A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

arXiv:2611.07309 · cs.CC · Submitted 2026-11-05 · Read on arXiv

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

Related papers