Metraipolis › archive › dc_481ff40b29e3
A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions — arXiv:2611.07309
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.07309
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:54:31.194Z
- SHA-256 of the archived text
49db61281ac5bfad347276f1be8db7fa98738506ed6077db6804108fde815dda- Stable URL of this page
https://metraipolis.com/documento/dc_481ff40b29e3
How to cite
A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions — arXiv:2611.07309 — arXiv (en), https://arxiv.org/abs/2611.07309 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_481ff40b29e3 (Metraipolis archive dc_481ff40b29e3, sha256 49db61281ac5bfad347276f1be8db7fa98738506ed6077db6804108fde815dda)
BibTeX
@misc{dc481ff40b29e3,
title = {A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions — arXiv:2611.07309},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.07309},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_481ff40b29e3; sha256 49db61281ac5bfad347276f1be8db7fa98738506ed6077db6804108fde815dda},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07309. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $\Gamma$ 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\subseteq\{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_\Gamma=\max_{R\in\Gamma}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_\Gamma}\operatorname{polylog} n)$-space randomized algorithm and an $\Omega_k(n^{d_\Gamma}/\log 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\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetilde\Theta(n)$ for insertion-only satisfiability, $\widetilde\Theta(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetilde\Theta(n^k)$ for exact optimization in either model.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.07309 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:27:27.632Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).