A Dichotomy Theorem for Multi-pass Streaming CSPs

In a constraint satisfaction problem (CSP) in the single-pass streaming model, an algorithm is given the constraints C1,…,Cm of an instance one after another (in some fixed order), and its goal is to approximate the value of the instance, i.e., the maximum fraction of constraints that can be satisfied simultaneously. In the p-pass streaming model the algorithm is given p passes over the input stream (in the same order), after which it is required to output an approximation of the value of the instance. We show a dichotomy result for p-pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter k, finite alphabet Σ, collection F of k-ary predicates over Σ and any c∈ (0,1), there exists 00 there is a constant pass, Oε(logn)-space randomized streaming algorithm solving cs−ε. That is, the algorithm accepts inputs with value at least c with probability at least 2/3, and rejects inputs with value at most s−ε with probability at least 2/3; (2) for all ε>0, any p-pass (even randomized) streaming algorithm that solves the promise problem MaxCSP(F)[c,s+ε] must use Ωε(n1/3/p) space. Our algorithm is based on a certain linear-programming relaxation of the CSP and on a distributed algorithm that approximates its value. This part builds on the works [Yoshida, STOC 2011] and [Saxena, Singer, Sudan, Velusamy, SODA 2025]. For our hardness result we show how to translate an integrality gap of the linear program into a family of hard instances, which we then analyze via studying a related communication complexity problem. That analysis is based on discrete Fourier analysis and builds on a prior work of the authors and on the work [Chou, Golovnev, Sudan, Velusamy, J.ACM 2024].