A Dichotomy Theorem for Multi-Pass Streaming CSPs

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_ (n) -space randomized streaming algorithm solving the promise problem MaxCSP (F) c, s-. 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 Ω_ (n^1/3/p) space. Our approximation 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, Velingker, Velusamy, J. ACM 2024.