A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions
cs.CC
Submitted: 2026-11-05
Updated: 2026-11-14
Comments: We have expanded our citations and added more context for the parameters studied in this paper
License: http://creativecommons.org/licenses/by/4.0/
The gist: We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language Γ of k-ary Boolean relations that is not…
Terminology
Abstract
We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language Γ of k-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For R 0,1 k, let d R be the minimum degree of an integer-coefficient polynomial vanishing exactly on R over the Boolean hypercube, and set d Γ= R inΓd R. On polynomial-length streams, we obtain an O k(n d Γ polylog n) -space randomized algorithm and an Ω k(n d Γ/ n) lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For k at least3, k-XOR with literals has three distinct space complexities: Θ(n) for insertion-only satisfiability, Θ(n k/2) for strict-turnstile satisfiability, and Θ(n k) for exact optimization in either model.
Sources
- Single-Pass Streaming CSPs via Two-Tier Sampling
- Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
- The Richness of CSP Non-redundancy
- Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
- On Weighted Graph Sparsification by Linear Sketching
- Near-Optimal Space Lower Bounds for Streaming CSPs
- Answer Set Programming for Stream Reasoning
- Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
- Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems
- Single Pass Spectral Sparsification in Dynamic Streams
- A Unified Theory of Sparsification
- Iterative Row Sampling
- Sketching approximations and LP approximations for finite CSPs are related
- Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
- Non-Redundancy of Low-Arity Symmetric Boolean CSPs
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?