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 0<s≤ c such that: 1. For any ε>0 there is a constant pass, Oε(log 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 Ωε(n1/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].