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).