arxiv: 2604.08731 · v1 · submitted 2026-04-09 · 💻 cs.CC · cs.DS

Recognition: unknown

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs

Noah G. Singer , Madhur Tulsiani , Santhoshini Velusamy

Authors on Pith no claims yet

Pith reviewed 2026-05-10 16:57 UTC · model grok-4.3

classification 💻 cs.CC cs.DS

keywords streaming algorithmsconstraint satisfaction problemsintegrality gapslower boundsapproximation algorithmssingle-pass streamingMax-CSP

0 comments

The pith

Any Max-CSP(F) whose basic LP has a (γ, β)-integrality gap requires linear space to distinguish (γ−ε)-satisfiable instances from (β+ε)-satisfiable ones in a single streaming pass.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for an arbitrary family of predicates F, no single-pass linear-space streaming algorithm can solve the gap version of Max-CSP(F) whenever the basic LP relaxation exhibits a (γ, β)-integrality gap. This holds for the promise problem of distinguishing instances with at least γ−ε fraction of satisfiable constraints from those with at most β+ε fraction. The result applies to all CSPs, not just those with special linear-algebraic structure, by identifying analytic analogues of prior conditions. The bound is tight: when no such gap exists, the LP itself can be simulated in sublinear space on bounded-degree instances, and every CSP admits a (1−ε)-approximation in quasilinear space.

Core claim

For arbitrary F ⊆ {0,1}^{[q]^k} and any ε > 0, whenever Max-CSP(F) admits a (γ, β)-integrality gap instance for the basic LP, every single-pass streaming algorithm distinguishing instances with at least γ−ε satisfiable constraints from those with at most β+ε satisfiable constraints requires Ω(n) space. The proof proceeds by reduction from the distributional implicit hidden partition problem, which carries the integrality-gap assumption into the single-pass linear-space setting.

What carries the argument

The reduction from the distributional implicit hidden partition problem, which inherits the (γ, β)-integrality gap of the basic LP while preserving the single-pass streaming model.

If this is right

The lower bound subsumes the linear-space result of Chou et al. (STOC 2022) that applied only to linear-algebraic CSPs.
Sublinear-space streaming algorithms can simulate the basic LP on bounded-degree instances and therefore achieve the best possible approximation ratio when no integrality gap exists.
Every CSP admits a (1−ε)-approximation in quasilinear space, showing the linear-space lower bound is tight up to the quasilinear vs linear distinction.
The single-pass lower bound is an analogue of the multi-pass result of Fei, Minzer, and Wang, but yields a stronger (linear) space bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Integrality gaps of the basic LP serve as the precise barrier for single-pass streaming approximability of all CSPs.
The analytic reformulation of the linear-algebraic conditions may allow similar lower bounds for other streaming problems or relaxations beyond the basic LP.
Multi-pass algorithms could potentially bypass the linear-space barrier on the same CSPs by using the underlying multi-pass reduction as a starting point.

Load-bearing premise

The reduction from the distributional implicit hidden partition problem works for arbitrary predicate families F and preserves the single-pass linear-space setting while inheriting the integrality-gap assumption.

What would settle it

A single-pass streaming algorithm that uses linear space and distinguishes Max-CSP(F) instances with at least γ−ε satisfiable constraints from those with at most β+ε satisfiable constraints, for some F whose basic LP has a (γ, β)-integrality gap.

Figures

Figures reproduced from arXiv: 2604.08731 by Madhur Tulsiani, Noah G. Singer, Santhoshini Velusamy.

**Figure 1.** Figure 1: below. The “variables” of this LP are distributions YC over [q] k for every constraint C ∈ supp(Φ). (Each such distribution can be encoded as q k − 1 standard LP variables.) An important fact about this LP is that it is a relaxation of the underlying CSP instance Φ: we always have 1 ≥ optLP(Φ) ≥ optCSP(Φ), where optLP(Φ) is the maximum feasible value for the LP. maximize E C=(f,e)∼Φ E a∼YC f(a) such th… view at source ↗

read the original abstract

For an arbitrary family of predicates $\mathcal{F} \subseteq \{0,1\}^{[q]^k}$ and any $\epsilon > 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 $\beta+\epsilon$ fraction of satisfiable constraints from instances of with at least $\gamma-\epsilon$ fraction of satisfiable constraints, whenever Max-CSP$({\mathcal{F}})$ admits a $(\gamma,\beta)$-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-\epsilon)$-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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) that match the basic LP integrality gap.

read the letter

The punchline is that this paper gives single-pass linear space lower bounds for the gap version of Max-CSP approximation that apply to any predicate family F whenever the basic LP has an integrality gap. It does this by reducing from the distributional implicit hidden partition problem of Fei Minzer and Wang, but in the single-pass setting. The key technical step is replacing the linear algebraic conditions from earlier papers with analytic analogues that work for general F. This subsumes the STOC 2022 result of Chou et al. and earlier work on Max-Cut. The paper handles the optimality side cleanly too. It points out that you can always get a (1-ε) approximation in quasilinear space, and that when there is no integrality gap the LP can be simulated in sublinear space on bounded degree instances. That shows the lower bound is tight. A minor concern is whether the analytic conditions are derived in a way that requires nothing beyond the existence of the gap instance. The abstract claims they do, and the reduction preserves the single-pass linear space hardness, but the construction details would need to be checked to make sure it applies universally without extra structure on F. This is a paper for the streaming and approximation algorithms community. Readers who care about space lower bounds for CSPs will find it directly useful as it unifies and extends several lines of work. It deserves a serious referee because the claim is general and the matching upper bounds are stated clearly. I recommend sending it for peer review.

Referee Report

1 major / 1 minor

Summary. The manuscript proves that for an arbitrary family of predicates F, there is a single-pass linear-space streaming lower bound for the gap promise problem on Max-CSP(F): distinguishing instances with at most β+ε fraction of satisfiable constraints from those with at least γ-ε, whenever the basic LP admits a (γ,β)-integrality gap. The proof reduces from the distributional implicit hidden partition problem of Fei, Minzer, and Wang (STOC 2026), by replacing linear-algebraic conditions with analytic analogues; this generalizes the linear-space lower bound of Chou et al. (STOC 2022) beyond CSPs with linear-algebraic structure. The bound is claimed to be essentially optimal given quasilinear-space (1-ε)-approximations and sublinear-space LP simulation on bounded-degree instances.

Significance. If correct, the result gives a tight, general characterization of single-pass streaming approximability for Max-CSPs in terms of basic LP integrality gaps, unifying and extending prior work on Max-Cut and structured CSPs. The analytic-conditions technique simplifies the proof while applying to a much larger class of predicates. Credit is due for the reduction-based approach and for explicitly tying the lower bound to the LP gap (with matching upper bounds noted).

major comments (1)

[main reduction section] Reduction from distributional implicit hidden partition (main technical section): the manuscript asserts that analytic analogues of the linear-algebraic conditions can be defined for arbitrary F solely from the existence of a (γ,β)-integrality gap instance. It must be shown explicitly that these analytic conditions are always satisfiable whenever such a gap exists, without requiring extra properties of F (e.g., specific correlation or Fourier decay behavior) not implied by the LP gap alone; otherwise the claim for arbitrary F fails.

minor comments (1)

The abstract states the result subsumes Chou et al. but does not quantify the space lower bound (e.g., Ω(n)); adding this would improve clarity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript. We address the sole major comment below.

read point-by-point responses

Referee: [main reduction section] Reduction from distributional implicit hidden partition (main technical section): the manuscript asserts that analytic analogues of the linear-algebraic conditions can be defined for arbitrary F solely from the existence of a (γ,β)-integrality gap instance. It must be shown explicitly that these analytic conditions are always satisfiable whenever such a gap exists, without requiring extra properties of F (e.g., specific correlation or Fourier decay behavior) not implied by the LP gap alone; otherwise the claim for arbitrary F fails.

Authors: We appreciate the referee drawing attention to this aspect of the reduction. The analytic conditions are constructed directly from any (γ,β)-integrality gap instance of the basic LP for the given F, without assuming extra structure such as linear-algebraic properties, specific correlations, or Fourier decay. In the main technical section, the gap instance supplies a fractional assignment achieving value γ and an integral assignment achieving value β; these are used to define the requisite test distributions and analytic expectations by averaging over the instance's variables and satisfying assignments. The resulting conditions hold by this averaging argument alone, which is independent of further properties of F. To address the request for explicit verification, we will insert a short lemma (with a self-contained proof) immediately preceding the reduction that derives the analytic conditions from the gap instance for arbitrary F. This addition will make the argument fully self-contained while preserving the generality of the claim. revision: yes

Circularity Check

0 steps flagged

No circularity: conditional lower bound via external reduction and LP-gap assumption

full rationale

The derivation starts from an external reduction to the distributional implicit hidden partition problem of Fei, Minzer, and Wang (STOC 2026) and conditions the streaming lower bound on the existence of a (γ,β)-integrality gap instance for the basic LP. Neither the gap instance nor the reduction is constructed or fitted inside the paper; both are independent inputs. The analytic analogues of linear-algebraic conditions are introduced as a technical device to extend the reduction to arbitrary predicate families F, without self-definition, renaming of known results, or load-bearing self-citation. The result is therefore self-contained against external benchmarks and does not reduce to its own outputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the existence of a (γ,β)-integrality gap instance for the basic LP (domain assumption) and the correctness of the reduction from the distributional implicit hidden partition problem (standard_math via prior work). No free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Existence of a (γ,β)-integrality gap instance for the basic LP relaxation of Max-CSP(F)
Invoked directly in the statement of the lower bound; the gap instance is the starting point for the streaming hardness.
standard math The distributional implicit hidden partition problem of Fei-Minzer-Wang admits a single-pass linear-space reduction that preserves the gap parameters
Cited as the starting point; correctness of this reduction is taken from prior work.

pith-pipeline@v0.9.0 · 5642 in / 1364 out tokens · 32654 ms · 2026-05-10T16:57:28.898638+00:00 · methodology

discussion (0)

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Characterizing Streaming Decidability of CSPs via Non-Redundancy
cs.DS 2026-04 unverdicted novelty 8.0

The single-pass streaming space complexity of CSP(Γ) is characterized up to a logarithmic factor by the non-redundancy NRD_n(Γ).
Characterizing Streaming Decidability of CSPs via Non-Redundancy
cs.DS 2026-04 unverdicted novelty 8.0

The single-pass streaming space complexity of CSP(Γ) is characterized up to log factors by the non-redundancy NRD_n(Γ) of the constraint language.
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
cs.DS 2026-05 conditional novelty 7.0

Symmetric Boolean CSP predicates of arity at most 5 have their non-redundancy NRD_n(R) classified as O(n^t) for small t, with all arity-4 cases and all but two arity-5 cases resolved via t-balancedness and OR-reductions.

Reference graph

Works this paper leans on

15 extracted references · 12 canonical work pages · cited by 2 Pith papers · 2 internal anchors

[1]

On quadratic threshold CSPs

arXiv:2604.01575 [cs]. Pre-published. [ABFS26] Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian. “Half-Approximating Maximum Dicut in the Streaming Setting”. In:Proceedings of the 58th ACM Symposium on Theory of Computing. STOC 2026 (June 22–26, 2026). Association for Computing Machinery,

work page arXiv 2026
[2]

Monochromatic Triangles, Triangle Listing and

[AKSY20] Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu. “Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems”. In:2020 IEEE 61st Annual Symposium on Foundations of Computer Science. FOCS 2020 (Nov. 16–19, 2020). IEEE Computer Society, Nov. 2020, pp. 354–364.DOI: 10.1109/FOCS46700.2020.0...

work page doi:10.1109/focs46700.2020.00041 2020
[3]

Sublinear

LIPIcs. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2018, 16:1–16:14.DOI:10.4230/LIPICS.ICALP.2018.16. [CGS+22] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. “Linear Space Streaming Lower Bounds for Approximating CSPs”. In:Proceedings of the 54th Annual ACM Symposium on Theory of Computing. STOC 2022 (Ju...

work page doi:10.4230/lipics.icalp.2018.16 2018
[4]

A Dichotomy Theorem for Multi-Pass Streaming CSPs

[FMW26a] Yumou Fei, Dor Minzer, and Shuo Wang. “A Dichotomy Theorem for Multi-Pass Streaming CSPs”. In:Proceedings of the 58th ACM Symposium on Theory of Computing. STOC 2026 (June 22– 26, 2026). To appear. Association for Computing Machinery,

2026
[5]

Near-Optimal Space Lower Bounds for Streaming CSPs

arXiv:2604.01400 [cs]. Pre-published. [Gri01] D. Grigoriev. “Complexity of Positivstellensatz Proofs for the Knapsack”. In:computational complexity10.2 (Dec. 1, 2001), pp. 139–154.DOI:10.1007/s00037-001-8192-0. [GT17] Mrinalkanti Ghosh and Madhur Tulsiani. “From Weak to Strong LP Gaps for All CSPs”. In: CCC 2017 (July 6–9, 2017). Ed. by Ryan O’Donnell. Vol

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00037-001-8192-0 2001
[6]

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017, 11:1–11:27.DOI:10.4230/LIPICS.CCC.2017.11. [GT19] Venkatesan Guruswami and Runzhou Tao. “Streaming Hardness of Unique Games”. In:Ap- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX 2019 (Sept. 20–22, 2019). Ed. by Dimitris Achlioptas and László A...

work page doi:10.4230/lipics.ccc.2017.11 2017
[7]

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

LIPIcs. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, Sept. 2019, 5:1–5:12.DOI: 10 . 4230 / LIPIcs.APPROX-RANDOM.2019.5. [GVV17] Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. “Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph”. In:Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tec...

2019
[8]

Schloss Dagstuhl — Leibniz-Zentrum für Informatik, Aug

LIPIcs. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, Aug. 2017, 8:1–8:19.DOI:

2017
[9]

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

4230/LIPIcs.APPROX-RANDOM.2017.8. [KK15] Dmitry Kogan and Robert Krauthgamer. “Sketching Cuts in Graphs and Hypergraphs”. In: Proceedings of the 6th Annual Conference on Innovations in Theoretical Computer Science. ITCS 2015 (Jan. 11–13, 2015). Association for Computing Machinery, 2015, pp. 367–376.DOI: 10.1145/ 2688073.2688093. [KK19] Michael Kapralov an...

work page doi:10.1145/3313276.3316364 2017
[10]

and MAKARYCHEV, Y

To appear. Association for Computing Machinery, June 19, 2017, pp. 132–145.DOI:10.1145/3055399.3055485. [KMR22] Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. “Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs”. In:SIAM Journal on Computing51.2 (Apr. 2022). Conference version in STOC 2017, STOC17-30...

work page doi:10.1145/3055399.3055485 2017
[11]

and Yu, Huacheng , editor =

LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, 80:1–80:15.DOI: 10.4230/LIPIcs.ITCS.2023.80. [Lee15] Euiwoong Lee. “Hardness of Graph Pricing Through Generalized Max-Dicut”. In:Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC 2015 (June 15–17, 2015). Portland, OR, USA: ACM, June 14, 2015, pp. 391–399.DOI:...

work page doi:10.4230/lipics.itcs.2023.80 2023
[12]

Dynamic set cover: improved algorithms and lower bounds , booktitle =

444 pp.ISBN: 978-1-107-03832-5. [Pot19] Aaron Potechin. “On the Approximation Resistance of Balanced Linear Threshold Functions”. In:Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC 2019 (June 23–26, 2019). Association for Computing Machinery, June 23, 2019, pp. 430–441.DOI: 10.1145/3313276.3316374. [Rag08] Prasad Raghavend...

work page doi:10.1145/3313276.3316374 2019
[13]

Singer, Madhur Tulsiani, and Santhoshini Velusamy

arXiv: 2509.17926 [cs] . Pre- published. [Sud22] Madhu Sudan. “Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk)”. In: 49th International Colloquium on Automata, Languages, and Programming. ICALP 2022 (July 4–8, 2022). Ed. by Mikołaj Boja ´ nczyk, Emanuela Merelli, and David P . Woodruff. Vol

work page arXiv 2022
[14]

URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs

LIPIcs. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2022, 5:1–5:20.DOI: 10.4230/LIPIcs. ICALP.2022.5. [Tul09] Madhur Tulsiani. “CSP Gaps and Reductions in the Lasserre Hierarchy”. In:Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. STOC 2009 (May 31–June 2, 2009). Bethesda, MD, USA: ACM, May 31, 2009, pp. 303–312.ISBN: 97...

work page doi:10.4230/lipics 2022
[15]

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes

arXiv:2512.19521 [cs]. Pre-published. 45 [Yao77] Andrew Chi-Chih Yao. “Probabilistic Computations: Toward a Unified Measure of Com- plexity”. In:Proceedings of the 18th Annual Symposium on Foundations of Computer Science. SFCS 1977 (Oct. 31–Nov. 2, 1977). IEEE Computer Society, Sept. 30, 1977, pp. 222–227.DOI: 10.1109/SFCS.1977.24. [Yos11] Yuichi Yoshida....

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/sfcs.1977.24 1977