Metraipolis › archive › dc_689e69d3ee3d
Stability Dichotomies for Boolean Constraint Satisfaction Problems — arXiv:2609.32357
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.32357
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:18:55.016Z
- SHA-256 of the archived text
3f7c8de4ab9dc252a67a819678436f0b67c49a7cf2fbc5baba5de4a4aa72cd44- Stable URL of this page
https://metraipolis.com/documento/dc_689e69d3ee3d
How to cite
Stability Dichotomies for Boolean Constraint Satisfaction Problems — arXiv:2609.32357 — arXiv (en), https://arxiv.org/abs/2609.32357 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_689e69d3ee3d (Metraipolis archive dc_689e69d3ee3d, sha256 3f7c8de4ab9dc252a67a819678436f0b67c49a7cf2fbc5baba5de4a4aa72cd44)
BibTeX
@misc{dc689e69d3ee3d,
title = {Stability Dichotomies for Boolean Constraint Satisfaction Problems — arXiv:2609.32357},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.32357},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_689e69d3ee3d; sha256 3f7c8de4ab9dc252a67a819678436f0b67c49a7cf2fbc5baba5de4a4aa72cd44},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32357. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the stability of Boolean constraint satisfaction problems (CSPs) through the notion of average sensitivity (Varma and Yoshida, SODA 2021; SICOMP 2023). It measures the expected $1$-Wasserstein distance between an algorithm's output distributions before and after the deletion of a uniformly chosen constraint, using the unnormalized Hamming metric. We establish two dichotomies for every finite Boolean constraint language $\Gamma$, where $n\geq 2$ denotes the number of variables in an instance. For stable solvability, exactly one of the following holds: $\bullet$ either there is an algorithm that solves $\mathrm{CSP}(\Gamma)$ and has average sensitivity $O_{\Gamma}(1)$ for all satisfiable instances; $\bullet$ or every algorithm that solves $\mathrm{CSP}(\Gamma)$ has average sensitivity $\Omega_{\Gamma}(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $\Gamma$ has finite duality: unsatisfiability can be witnessed on a bounded number of variables. For stable approximability, where a $(1-\varepsilon)$-approximation violates at most an $\varepsilon$-fraction of the constraints in expectation, exactly one of the following holds: $\bullet$ either for every $\varepsilon\in(0,1]$, there is an algorithm that $(1-\varepsilon)$-approximates $\mathrm{CSP}(\Gamma)$ with average sensitivity $O_{\Gamma}(\varepsilon^{-1}\log n)$ for all satisfiable instances; $\bullet$ or there exists $\varepsilon_{\Gamma}\in(0,1]$ such that every algorithm that $(1-\varepsilon_{\Gamma})$-approximates $\mathrm{CSP}(\Gamma)$ has average sensitivity $\Omega_{\Gamma}(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $\Gamma$ has bounded width: local consistency checks on bounded sets of variables detect unsatisfiability.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.32357 — 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-10-07T23:56:21.749Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).