Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Provides tight streaming lower bounds for a broad class of constraint satisfaction problems, resolving a key question in streaming complexity.
The authors prove optimal single-pass streaming lower bounds for approximating Max-CSPs, showing that linear space is necessary whenever the basic LP has an integrality gap. This generalizes prior results to all CSPs and matches known upper bounds.
For an arbitrary family of predicates $\mathcal{F} \subseteq \{0,1\}^{[q]^k}$ and any $ε> 0$, we prove a single-pass, linear-space streaming lower bound against the gap promise problem of distinguishing instances of Max-CSP$({\mathcal{F}})$ with at most $β+ε$ fraction of satisfiable constraints from instances of with at least $γ-ε$ fraction of satisfiable constraints, whenever Max-CSP$({\mathcal{F}})$ admits a $(γ,β)$-integrality gap instance for the basic LP. This subsumes the linear-space lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC 2022), which applies only to a special subclass of CSPs with linear-algebraic structure. (Their result itself generalizes work of Kapralov and Krachun (STOC 2019) for Max-CUT.) Our approach identifies the right ``analytic'' analogues of previously-used linear-algebraic conditions; this yields substantial simplifications while capturing a much larger class of problems. Our lower bound is essentially optimal for single-pass streaming, since: (1) All CSPs admit $(1-ε)$-approximations in quasilinear space, and (2) sublinear-space streaming algorithms can simulate the LP (on bounded-degree instances), giving approximation algorithms when integrality gap instances do not exist. The starting point for our lower bound is a reduction from a "distributional implicit hidden partition'' problem defined by Fei, Minzer, and Wang (STOC 2026) in the context of multi-pass streaming. Our result is an analogue of theirs in the single-pass setting, where we obtain a much stronger (and tight) space lower bound.