A Dichotomy Theorem for Multi-Pass Streaming CSPs

Abstract

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 $\hat{I}\pounds$, collection $\mathcal{F}$ of $k$-ary predicates over $\hat{I}\pounds$ and any $c\in (0,1)$, there exists $0<s\le c$ such that: 1. For any $\epsilon >0$ there is a constant pass, $O_{\epsilon }(\log n)$-space randomized streaming algorithm solving the promise problem $\text{MaxCSP}(\mathcal{F})[c,s-\epsilon ]$. 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-\epsilon$ with probability at least $2/3$. 2. For all $\epsilon >0$, any $p$-pass (even randomized) streaming algorithm that solves the promise problem $\text{MaxCSP}(\mathcal{F})[c,s+\epsilon ]$ must use $\hat{I}{\text{c◯}}_{\epsilon }(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, Velusamy, J.ACM 2024].

various minor errors corrected in the second version