arxiv: 2604.21922 · v2 · submitted 2026-04-23 · 💻 cs.DS · cs.CC

Recognition: no theorem link

Characterizing Streaming Decidability of CSPs via Non-Redundancy

Amatya Sharma , Santhoshini Velusamy

Authors on Pith no claims yet

Pith reviewed 2026-05-14 21:39 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords constraint satisfaction problemsstreaming algorithmsspace complexitynon-redundancysatisfiabilityconstraint languages

0 comments

The pith

The single-pass streaming space complexity of CSP(Γ) is characterized up to a logarithmic factor by the non-redundancy measure NRD_n(Γ).

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

The paper establishes that the memory required to decide satisfiability of a constraint satisfaction problem in the single-pass streaming model is governed by a structural property of the constraint language. Specifically, this property is the maximum number of constraints on n variables such that each one remains non-redundant, meaning the rest of the set stays satisfiable when it is removed. A reader would care because earlier results gave tight bounds only for special cases such as k-SAT, while general CSPs had only a weak linear lower bound; the new parameter unifies these under one quantity. If the characterization holds, it supplies both matching upper and lower bounds for every finite constraint language, explaining why some CSPs need far more space than others.

Core claim

The single-pass streaming space complexity of CSP(Γ) is characterized, up to a logarithmic factor, by NRD_n(Γ), defined as the largest number of constraints over n variables such that every constraint is non-redundant: there exists an assignment satisfying all the others.

What carries the argument

The non-redundancy parameter NRD_n(Γ), the maximum size of a set of constraints on n variables where removing any single constraint leaves the remaining set satisfiable.

Load-bearing premise

The non-redundancy parameter NRD_n(Γ) fully captures the streaming hardness for every finite constraint language Γ in the single-pass model.

What would settle it

A finite constraint language Γ for which the single-pass streaming space complexity differs from NRD_n(Γ) by more than a logarithmic factor.

read the original abstract

We study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language $\Gamma$, that is, a finite set of $k$-ary relations over the domain $[q] = \{0, \dots, q-1\}$. An instance of $\mathsf{CSP}(\Gamma)$ consists of $m$ constraints over $n$ variables $x_1, \ldots, x_n$ taking values in $[q]$. Each constraint $C_i$ is of the form $\{R_i,(x_{i_1} + \lambda_{i_1}, \ldots, x_{i_k} + \lambda_{i_k})\}$, where $R_i \in \Gamma$ and $\lambda_{i_1}, \ldots, \lambda_{i_k} \in [q]$ are constants; it is satisfied if and only if $(x_{i_1} + \lambda_{i_1}, \ldots, x_{i_k} + \lambda_{i_k}) \in R_i$, where addition is modulo $q$. In the streaming model, constraints arrive one by one, and the goal is to determine, using minimum memory, whether there exists an assignment satisfying all constraints. For $k$-SAT, Vu (TCS 2024) proves an optimal $\Omega(n^k)$ space lower bound, while for general CSPs, Chou, Golovnev, Sudan, and Velusamy (JACM 2024) establish an $\Omega(n)$ lower bound; a complete characterization has remained open. We close this gap by showing that the single-pass streaming space complexity of $\mathsf{CSP}(\Gamma)$ is precisely governed by its non-redundancy, a structural parameter introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020). The non-redundancy $\mathsf{NRD}_n(\Gamma)$ is the maximum number of constraints over $n$ variables such that every constraint $C$ is non-redundant, i.e., there exists an assignment satisfying all constraints except $C$. We prove that the single-pass streaming complexity of $\mathsf{CSP}(\Gamma)$ is characterized, up to a logarithmic factor, by $\mathsf{NRD}_n(\Gamma)$.

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

The paper fully characterizes single-pass streaming CSP complexity via the non-redundancy parameter NRD_n(Γ), up to logs.

read the letter

The punchline is that this paper gives a full characterization of the single-pass streaming complexity of CSP(Γ) in terms of the non-redundancy parameter NRD_n(Γ) from prior work. The space is Θ(NRD_n(Γ)) up to logs for any finite Γ. What is new is the complete result that covers all cases, not just special ones like SAT. The paper does well by providing both the algorithmic upper bound and the hardness lower bound that match. The upper bound maintains a basis of at most NRD_n(Γ) constraints as they stream in, which allows deciding satisfiability with that space. For the lower bound, they reduce from a problem where the number of non-redundant constraints forces the space usage. This approach is consistent and uses the definition directly without additional assumptions on the arrival order or the domain. The soft spots are minor. The log factors mean it's not asymptotically tight without them, but the paper states the characterization with those factors, so it's accurate. There might be room to remove the logs in some cases, but that's not a flaw in the current work. The paper focuses on single-pass, which is the model where the gap was open, so that's appropriate. This is the kind of paper that researchers in theoretical computer science working on streaming and complexity will want to read. It gives a useful parameter for classifying CSPs by their streaming requirements. The thinking is clear and the engagement with previous bounds is direct. I would cite this if I were working on related streaming lower bounds. It deserves a serious referee because the result is grounded in matching upper and lower bounds.

Referee Report

0 major / 2 minor

Summary. The paper proves that the single-pass streaming space complexity of deciding satisfiability for CSP(Γ), where Γ is a finite constraint language over domain [q], is characterized up to logarithmic factors by the non-redundancy parameter NRD_n(Γ), defined as the maximum number of non-redundant constraints over n variables (each constraint remains satisfiable when removed from the set). This is shown via matching upper and lower bounds in the single-pass model with arbitrary arrival order.

Significance. If the result holds, it supplies the first complete characterization of single-pass streaming complexity for general CSPs, extending prior Ω(n^k) bounds for k-SAT and Ω(n) bounds for general CSPs. The work directly ties a structural CSP parameter (NRD_n from prior literature) to streaming space via consistent application in both the hardness reduction and the algorithmic construction that maintains a basis of size at most NRD_n(Γ).

minor comments (2)

[Introduction] §1, paragraph on prior work: the citation to Chou et al. (JACM 2024) for the Ω(n) lower bound could include a brief parenthetical on the precise model (single-pass vs. multi-pass) to aid readers.
[Preliminaries] Definition 2.3: the notation for shifted constraints (x + λ) is clear but the text could add one sentence confirming that addition is componentwise modulo q for all relations in Γ.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript and for recommending acceptance. We are pleased that the referee recognizes the significance of providing the first complete characterization (up to logarithmic factors) of single-pass streaming space complexity for general CSP(Γ) in terms of the non-redundancy parameter NRD_n(Γ).

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper takes the structural parameter NRD_n(Γ) from independent prior work (Bessiere et al., AAAI 2020) and proves a new theorem establishing that single-pass streaming space complexity of CSP(Γ) is Θ(NRD_n(Γ)) up to logarithmic factors. The upper bound follows from an explicit streaming algorithm that maintains a non-redundant basis of size at most NRD_n(Γ); the lower bound follows from a direct reduction that produces hard instances whose non-redundancy is preserved by construction. Neither bound reduces the claimed characterization to a fitted parameter, a self-citation, or a definitional tautology; the derivation is self-contained against the external definition of non-redundancy and the standard single-pass streaming model.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the definition of non-redundancy from prior work and standard assumptions of the single-pass streaming model; no new free parameters or invented entities are introduced.

axioms (1)

domain assumption Single-pass streaming model with constraints arriving sequentially and space measured in bits
Standard model used throughout the streaming literature cited in the abstract.

pith-pipeline@v0.9.0 · 5741 in / 1181 out tokens · 31079 ms · 2026-05-14T21:39:44.315399+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Forward citations

Cited by 1 Pith paper

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

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

13 extracted references · 13 canonical work pages · cited by 1 Pith paper · 2 internal anchors

[1]

& Sena, C

arXiv:2604.01575 [cs]. Pre-published. [Abl96] Farid Ablayev. “Lower bounds for one-way probabilistic communication complexity and their application to space complexity”. In:Theoretical Computer Science157.2 (1996), pp. 139–159. ISSN: 0304-3975.DOI: https : / / doi . org / 10 . 1016 / 0304 - 3975(95 ) 00157 - 3.URL: https : //www.sciencedirect.com/science/...

work page doi:10.1007/978- 1996
[2]

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT

Ed. by David Zuckerman. IEEE Computer Society, 2019, pp. 180–201.DOI: 10.1109/FOCS.2019.00021.URL:https://doi.org/10.1109/FOCS.2019.00021. [ALMS25] Aditya Anand, Euiwoong Lee, Davide Mazzali, and Amatya Sharma. “Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT”. In:Approximation, Random- ization, and Combinatorial Optimiz...

work page doi:10.1109/focs.2019.00021.url:https://doi.org/10.1109/focs.2019.00021 2019
[3]

Near-Optimal Space Lower Bounds for Streaming CSPs

arXiv:2604.01400 [cs]. Pre-published. [FV98] Tom´as Feder and Moshe Y Vardi. “The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory”. In:SIAM Journal on Computing28.1 (1998), pp. 57–104. [GS11] Venkatesan Guruswami and Ali Kemal Sinop. “Lasserre hierarchy, higher eigenvalues, and approxim...

work page internal anchor Pith review Pith/arXiv arXiv 1998
[4]

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

LIPIcs. 2017, 11:1–11:27.DOI:10.4230/LIPICS.CCC.2017.11. [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 Techniques. APPROX 2017 (Aug. 16–18, 2017). Ed. by Klaus Jansen, Jos ´e ...

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

Schloss Dagstuhl — Leibniz-Zentrum f ¨ur Informatik, Aug

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

work page 2017
[6]

Some optimal inapproximability results

4230/LIPIcs.APPROX-RANDOM.2017.8. [H˚as01] Johan H˚astad. “Some optimal inapproximability results”. In:Journal of the ACM (JACM)48.4 (2001), pp. 798–859. [JCG97] Peter Jeavons, David Cohen, and Marc Gyssens. “Closure properties of constraints”. In:Journal of the ACM (JACM)44.4 (1997), pp. 527–548. [JP19] Bart MP Jansen and Astrid Pieterse. “Optimal sparsi...

work page 2017
[7]

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

[KK19] Michael Kapralov and Dmitry Krachun. “An Optimal Space Lower Bound for Approximating MAX-CUT”. In:Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC (June 23–26, 2019). Association for Computing Machinery, June 2019, pp. 277–288.DOI: 10.1145/3313276.3316364. [KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan...

work page doi:10.1145/3313276.3316364 2019
[8]

Linear time approximation schemes for the Gale- Berlekamp game and related minimization problems

LIPIcs. Schloss Dagstuhl– Leibniz-Zentrum f ¨ur Informatik, 2023, 80:1–80:15.DOI: 10.4230/LIPIcs.ITCS.2023.80.URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.80. [KS09] Marek Karpinski and Warren Schudy. “Linear time approximation schemes for the Gale- Berlekamp game and related minimization problems”. In:Proceedings of the forty...

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

Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems

Ed. by David B. Shmoys. ACM, 2014, pp. 634–643.DOI: 10.1145/2591796. 2591817.URL:https://doi.org/10.1145/2591796.2591817. [Kuc25] Sahil Kuchlous.Streaming Algorithms for Code Sparsification

work page doi:10.1145/2591796 2014
[10]

Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems

[LLZ02] Michael Lewin, Dror Livnat, and Uri Zwick. “Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems”. In:International Conference on Integer Programming and Combinatorial Optimization. Springer. 2002, pp. 67–82. [LW20] Victor Lagerkvist and Magnus Wahlstr ¨om. “Sparsification of SAT and CSP problems via tractable extensions”. In:ACM...

work page 2002
[11]

Optimal algorithms and inapproximability results for every CSP?

[Rag08] Prasad Raghavendra. “Optimal algorithms and inapproximability results for every CSP?” In: Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008, pp. 245–254. [Sch78] Thomas J. Schaefer. “The Complexity of Satisfiability Problems”. In:Proceedings of the 10th ACM Symposium on Theory of Computing (STOC). ACM, 1978, pp. 216–226...

work page arXiv 2008
[12]

May 2023.DOI: 10.4230/ LIPIcs.APPROX/RANDOM.2023.15

LIPIcs. May 2023.DOI: 10.4230/ LIPIcs.APPROX/RANDOM.2023.15. [STV25] Noah G. Singer, Madhur Tulsiani, and Santhoshini Velusamy.Sketching Approximations and LP Approximations for Finite CSPs Are Related. Sept. 23,

work page 2023
[13]

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs

arXiv:2604.08731 [cs]. Pre-published. [Vu24] Hoa T Vu. “Revisiting maximum satisfiability and related problems in data streams”. In: Theoretical Computer Science982 (2024), p. 114271. [Zhu20] Dmitriy Zhuk. “A proof of the CSP dichotomy conjecture”. In:Journal of the ACM (JACM)67.5 (2020), pp. 1–78. 19

work page internal anchor Pith review Pith/arXiv arXiv 2024