Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910118259458048 |
|---|---|
| author | Singer, Noah G. Tulsiani, Madhur Velusamy, Santhoshini |
| author_facet | Singer, Noah G. Tulsiani, Madhur Velusamy, Santhoshini |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_08731 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs Singer, Noah G. Tulsiani, Madhur Velusamy, Santhoshini Computational Complexity Data Structures and Algorithms 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. |
| title | Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.08731 |