arxiv: 2604.01400 · v1 · submitted 2026-04-01 · 💻 cs.CC · cs.DS

Recognition: 2 theorem links

· Lean Theorem

Near-Optimal Space Lower Bounds for Streaming CSPs

Yumou Fei , Dor Minzer , Shuo Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-13 21:22 UTC · model grok-4.3

classification 💻 cs.CC cs.DS

keywords streaming algorithmsconstraint satisfactionspace lower boundsapproximation algorithmsFourier analysislinear programming relaxationsmulti-pass streaming

0 comments

The pith

For any CSP, p-pass streaming algorithms need Ω(√n/p) space to beat the basic LP approximation threshold.

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

The paper proves that in the streaming model where constraints arrive in fixed order, any algorithm that achieves an approximation factor better than the one given by the basic linear program must use Ω(√n/p) space across p passes. This improves the earlier n^{1/3}/p bound and is nearly tight for the gap version of the problem. When the number of passes is o(log n), the space requirement strengthens to Ω(n · 2^{-O(p)}), showing that even single-pass sublinear-space algorithms cannot exceed the LP threshold on bounded-degree instances. For some specific CSPs the bound reaches Ω(n/p) for any constant-factor approximation strictly below 1.

Core claim

For every constraint satisfaction problem and every ε > 0, any p-pass streaming algorithm that returns an (α_LP + ε)-approximation to the maximum fraction of satisfiable constraints requires Ω(√n/p) space; when p = o(log n) the lower bound becomes Ω(n · 2^{-O_ε(p)}). For certain CSPs there exists α < 1 such that an α-approximation already needs Ω(n/p) space. The proofs are obtained by Fourier-analytic reductions that build on hard input distributions constructed from the basic LP.

What carries the argument

Fourier-ℓ1 lower-bound reduction applied to hard streaming instances whose Fourier spectrum encodes the gap between the basic LP value and any better approximation.

If this is right

The previous Ω(n^{1/3}/p) space lower bound is improved to the nearly tight Ω(√n/p) bound.
α_LP is the best possible approximation achievable by any single-pass sublinear-space algorithm on bounded-degree instances.
For p = o(log n) the space requirement becomes nearly linear in n.
Certain CSPs require Ω(n/p) space for any approximation factor strictly below 1.

Where Pith is reading between the lines

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

The same Fourier technique may extend to other streaming optimization problems whose relaxations are captured by linear programs.
If the input order can be chosen adversarially rather than fixed, the quantitative bounds might change.
The exponential dependence on p suggests that even a logarithmic number of passes still forces super-polylogarithmic space.

Load-bearing premise

The input arrives in one fixed order and the hard distribution is exactly the one for which the Fourier-analytic reduction applies.

What would settle it

A p-pass streaming algorithm that achieves (α_LP + ε)-approximation for every CSP using o(√n/p) space on the hard instances would falsify the main claim.

read the original abstract

In a streaming constraint satisfaction problem (streaming CSP), a $p$-pass algorithm receives the constraints of an instance sequentially, making $p$ passes over the input in a fixed order, with the goal of approximating the maximum fraction of satisfiable constraints. We show near optimal space lower bounds for streaming CSPs, improving upon prior works. (1) Fei, Minzer and Wang (\textit{STOC 2026}) showed that for any CSP, the basic linear program defines a threshold $\alpha_{\mathrm{LP}}\in [0,1]$ such that, for any $\varepsilon > 0$, an $(\alpha_{\mathrm{LP}} - \varepsilon)$-approximation can be achieved using constant passes and polylogarithmic space, whereas achieving $(\alpha_{\mathrm{LP}} + \varepsilon)$-approximation requires $\Omega(n^{1/3}/p)$ space. We improve this lower bound to $\Omega(\sqrt{n}/p)$, which is nearly tight for a gap version of the problem. (2) For $p=o(\log n)$, we further strengthen the lower bound to $\Omega(n\cdot2^{-O_{\varepsilon}(p)})$. Combined with existing algorithmic results, this shows that $\alpha_{\mathrm{LP}}$ is not only the limit of multi-pass polylogarithmic-space algorithms, but also the limit of single-pass sublinear-space algorithms on bounded-degree instances. (3) For certain CSPs, we show that there exists $\alpha < 1$ such that achieving an $\alpha$-approximation requires $\Omega(n/p)$ space. Our proofs are Fourier analytic, building on the techniques of Fei, Minzer and Wang (\textit{STOC 2026}) and the Fourier-$\ell_1$-based lower bound method of Kapralov and Krachun (\textit{STOC 2019}).

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 tightens the streaming CSP space lower bound from n^{1/3}/p to sqrt(n)/p via refined Fourier-l1 analysis, nearly matching known upper bounds for gap versions.

read the letter

The main news is the jump in the space lower bound for any CSP: achieving an (alpha_LP + eps)-approximation now requires Omega(sqrt(n)/p) space instead of the prior Omega(n^{1/3}/p). For p = o(log n) they strengthen it further to Omega(n * 2^{-O_eps(p)}), and for some CSPs they reach Omega(n/p) for constant-factor approximation below 1. These are the concrete quantitative improvements, and they line up with existing multi-pass polylog algorithms to pin alpha_LP as the actual threshold for sublinear-space regimes on bounded-degree instances. The work does this by sharpening the Fourier-l1 reduction from the STOC 2026 paper (by two of the same authors) and the Kapralov-Krachun technique, with the key step being tighter control on the spectrum of the hard distribution across passes. That refinement is what delivers the sqrt(n) exponent and looks like the real technical lift. The proofs stay within established Fourier-analytic territory rather than introducing new machinery, which keeps the argument grounded. The main soft spot is that the abstract gives no explicit error bounds or degree-isolation lemmas, so it is still possible the multi-pass communication reduction leaks a little when higher-degree terms become visible; if that happens the claimed improvement would shrink. The fixed-order input assumption is standard but does limit how far the result travels to fully adaptive streams. Overall the paper is for people who track streaming lower bounds and CSP approximation thresholds. A reader who already knows the STOC 2026 result will see the clearest value in the exponent improvement and the single-pass implication. It is worth sending to peer review because the bound is now close to tight on the gap version and the argument connects directly to known algorithms without circularity.

Referee Report

3 major / 3 minor

Summary. The manuscript establishes improved space lower bounds for p-pass streaming algorithms that approximate the maximum fraction of satisfiable constraints in a CSP instance. For any CSP and ε>0, any algorithm achieving an (α_LP + ε)-approximation requires Ω(√n/p) space; when p=o(log n) the bound strengthens to Ω(n·2^{-O_ε(p)}). For certain CSPs an α-approximation with α<1 requires Ω(n/p) space. The proofs are Fourier-analytic and build directly on the hard distributions and ℓ1-reduction technique of Fei-Minzer-Wang (STOC 2026) together with the communication lower-bound method of Kapralov-Krachun (STOC 2019).

Significance. If the central Fourier-ℓ1 reduction is correct, the results nearly close the gap between the known polylog-space multi-pass upper bounds and the space lower bounds, establishing that α_LP is the precise threshold for both polylog-space multi-pass algorithms and sublinear-space single-pass algorithms on bounded-degree instances. The improvement from n^{1/3} to √n is quantitatively meaningful and the exponential strengthening for small p is new.

major comments (3)

[§3.2] §3.2, the Fourier-ℓ1 reduction (Lemma 3.4): the argument that the p-pass streaming algorithm induces a communication protocol whose advantage is controlled by the low-degree Fourier mass of the hard distribution must be made fully explicit. The manuscript improves the exponent from n^{1/3} to √n precisely by tightening the spectral concentration; any unaccounted leakage of higher-degree mass across the p sequential passes would weaken the claimed Ω(√n/p) bound.
[§4.1] §4.1, the communication lower bound (Theorem 4.3): the reduction from the p-pass streaming problem to a two-party communication problem assumes a fixed input order and non-adaptive queries within each pass. The paper should state the precise communication complexity lower bound used and verify that it remains Ω(√n) even after the p-fold composition.
[§5] §5, the strengthened bound for p=o(log n) (Theorem 1.2): the exponential dependence 2^{-O_ε(p)} is derived from an iterated application of the base reduction. A concrete calculation showing how the constant in the O_ε(p) term arises from the degree truncation and the number of passes is needed to confirm the bound does not degrade faster than claimed.

minor comments (3)

[Abstract] The abstract and introduction cite Fei-Minzer-Wang as STOC 2026; the full bibliographic entry should appear in the references section.
[§2] Notation for the LP threshold α_LP is introduced only in the abstract; a self-contained definition (or pointer to the precise LP) should be given in §2.
[Figure 1] Figure 1 (the comparison of space bounds) uses a log-log scale; the caption should explicitly label the prior n^{1/3} curve and the new √n curve for clarity.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions, which will help clarify the technical arguments. We address each major comment below and will incorporate the requested expansions in the revised manuscript.

read point-by-point responses

Referee: [§3.2] §3.2, the Fourier-ℓ1 reduction (Lemma 3.4): the argument that the p-pass streaming algorithm induces a communication protocol whose advantage is controlled by the low-degree Fourier mass of the hard distribution must be made fully explicit. The manuscript improves the exponent from n^{1/3} to √n precisely by tightening the spectral concentration; any unaccounted leakage of higher-degree mass across the p sequential passes would weaken the claimed Ω(√n/p) bound.

Authors: We agree that the induction in the proof of Lemma 3.4 should be expanded for full explicitness. In the revision we will add a detailed paragraph (and a short auxiliary claim) showing how a p-pass streaming algorithm with space s is simulated by a p-round two-party protocol whose advantage is at most the low-degree Fourier mass of the hard distribution plus an additive error controlled by the spectral concentration bound from Fei-Minzer-Wang. Because the hard distribution is chosen so that its degree-d mass is 1−o(1) for d=Θ(√n), any higher-degree leakage across passes is absorbed into the o(1) term and does not degrade the Ω(√n/p) bound. revision: yes
Referee: [§4.1] §4.1, the communication lower bound (Theorem 4.3): the reduction from the p-pass streaming problem to a two-party communication problem assumes a fixed input order and non-adaptive queries within each pass. The paper should state the precise communication complexity lower bound used and verify that it remains Ω(√n) even after the p-fold composition.

Authors: We will revise the statement of Theorem 4.3 to cite the exact two-party lower bound of Kapralov-Krachun (STOC 2019, Theorem 1.1) for the fixed-order, non-adaptive query model. We will also add a short paragraph verifying the p-fold composition: because the input order is fixed globally and each pass corresponds to one communication round without reordering or adaptivity on the underlying instance, the Ω(√n) lower bound applies independently to each “block” and the total communication remains Ω(√n) after p rounds. revision: yes
Referee: [§5] §5, the strengthened bound for p=o(log n) (Theorem 1.2): the exponential dependence 2^{-O_ε(p)} is derived from an iterated application of the base reduction. A concrete calculation showing how the constant in the O_ε(p) term arises from the degree truncation and the number of passes is needed to confirm the bound does not degrade faster than claimed.

Authors: We will insert an explicit calculation in §5. Let d = Θ(1/ε) be the truncation degree. Each application of the base Fourier-ℓ1 reduction multiplies the advantage by at most 2^{-Ω(d)} plus an additive O(1/n) term. After p sequential passes the total advantage is therefore at most 2^{-Ω_ε(p)} + p·O(1/n). For p = o(log n) the additive term is negligible, yielding the claimed Ω(n·2^{-O_ε(p)}) space lower bound. The revised text will display the recurrence and the choice of constants. revision: yes

Circularity Check

0 steps flagged

No circularity: lower bounds derived from independent Fourier-ℓ1 reduction on externally cited hard instances

full rationale

The paper's core derivation improves an existing Ω(n^{1/3}/p) space lower bound to Ω(√n/p) via a tightened Fourier-analytic argument that maps p-pass streaming algorithms to communication protocols. This rests on the Fourier-ℓ1 method of Kapralov and Krachun (STOC 2019), an external reference, together with a hard distribution whose construction is attributed to the authors' prior STOC 2026 work. The improvement itself consists of new spectral concentration analysis rather than re-using fitted parameters, self-definitions, or renaming known results. No equation or step reduces by construction to the target bound; the cited prior result supplies only the base hard instances and is not invoked as a uniqueness theorem or load-bearing ansatz for the new exponent. The derivation is therefore self-contained against the stated external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard Fourier analysis of boolean functions and prior streaming lower-bound techniques; no free parameters, ad-hoc axioms, or new invented entities are introduced in the abstract.

axioms (1)

standard math Fourier analysis applies to the indicator functions of constraints in the streaming model
Invoked to obtain the space lower bounds as described in the abstract.

pith-pipeline@v0.9.0 · 5650 in / 1227 out tokens · 50324 ms · 2026-05-13T21:22:13.001824+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our proofs are Fourier analytic, building on the techniques of Fei, Minzer and Wang (STOC 2026) and the Fourier-ℓ1-based lower bound method of Kapralov and Krachun (STOC 2019).
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_strictMono_of_one_lt unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The weight of a restriction ∥ζ∥ = sum |Vi|^2 over connected components of exposed edges.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 4 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.
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
cs.CC 2026-04 unverdicted novelty 8.0

Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.
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

16 extracted references · 16 canonical work pages · cited by 3 Pith papers · 1 internal anchor

[1]

Half- approximating maximum dicut in the streaming setting

[ABFS25] Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian. Half- approximating maximum dicut in the streaming setting. CoRR, abs/2512.22729,

work page arXiv
[2]

Saxena, and Huacheng Yu

[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) , pages 354–364,

work page 2020
[3]

Graph streaming lower bounds for parameter estima- tion and property testing via a streaming xor lemma

[AN21] Sepehr Assadi and Vishvajeet N. Graph streaming lower bounds for parameter estima- tion and property testing via a streaming xor lemma. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , STOC 2021, page 612–625, New York, NY, USA,

work page 2021
[4]

Optimal streaming approximations for all boolean max-2csps and max-ksat

[CGV20] Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. Optimal streaming approximations for all boolean max-2csps and max-ksat. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 330–341. IEEE,

work page 2020
[5]

Unbounded-width csps are untestable in a sublinear number of queries

[Fei25] Yumou Fei. Unbounded-width csps are untestable in a sublinear number of queries. arXiv preprint arXiv:2510.27012 ,

work page arXiv
[6]

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut

[FMW25a] Yumou Fei, Dor Minzer, and Shuo Wang. Multi-Pass Streaming Lower Bounds for Approximating Max-Cut . In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1537–1560, Los Alamitos, CA, USA, December

work page 2025
[7]

[FMW25b] Yumou Fei, Dor Minzer, and Shuo Wang

IEEE Computer Society. [FMW25b] Yumou Fei, Dor Minzer, and Shuo Wang. A dichotomy theorem for multi-pass stream- ing csps. arXiv preprint arXiv:2509.11399 ,

work page arXiv
[8]

Query-to-communication lifting for bpp

[GPW17] Mika G¨ o¨ os, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for bpp. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 132–143. IEEE,

work page 2017
[9]

Streaming com- plexity of approximating max 2csp and max acyclic subgraph

[GVV17] Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. Streaming com- plexity of approximating max 2csp and max acyclic subgraph. In Approximation, Ran- domization, and Combinatorial Optimization. Algorithms and Techniques (APPROX- /RANDOM 2017), pages 8–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

work page 2017
[10]

Oblivious algorithms for maximum directed cut: New upper and lower bounds.arXiv preprint arXiv:2411.12976,

[HSV24] Samuel Hwang, Noah G Singer, and Santhoshini Velusamy. Oblivious algorithms for maximum directed cut: New upper and lower bounds.arXiv preprint arXiv:2411.12976,

work page arXiv
[11]

[Sin25] Noah G. Singer. Nine lower bound conjectures on streaming approximation algorithms for csps. CoRR, abs/2510.10714,

work page arXiv
[12]

Improved streaming algorithms for maximum directed cut via smoothed snapshots

[SSSV23] Raghuvansh R Saxena, Noah G Singer, Madhu Sudan, and Santhoshini Velusamy. Improved streaming algorithms for maximum directed cut via smoothed snapshots. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 855–870. IEEE,

work page 2023
[13]

Streaming algorithms via local algorithms for maximum directed cut

[SSSV25] Raghuvansh R Saxena, Noah G Singer, Madhu Sudan, and Santhoshini Velusamy. Streaming algorithms via local algorithms for maximum directed cut. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3392–3408. SIAM,

work page 2025
[14]

Singer, Madhur Tulsiani, and Santhoshini Velusamy

[STV25] Noah G. Singer, Madhur Tulsiani, and Santhoshini Velusamy. Sketching approximations and LP approximations for finite csps are related. CoRR, abs/2509.17926,

work page arXiv
[15]

Streaming and sketching complexity of csps: A survey

[Sud22] Madhu Sudan. Streaming and sketching complexity of csps: A survey. arXiv preprint arXiv:2205.02744,

work page arXiv
[16]

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

[Vel25] Santhoshini Velusamy. Near-optimal streaming approximation for max-dicut in sublin- ear space using two passes. CoRR, abs/2512.19521,

work page internal anchor Pith review Pith/arXiv arXiv