Stability Dichotomies for Boolean Constraint Satisfaction Problems

Abstract

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\ge 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-\epsilon )$-approximation violates at most an $\epsilon$-fraction of the constraints in expectation, exactly one of the following holds: $\bullet$ either for every $\epsilon \in (0,1]$, there is an algorithm that $(1-\epsilon )$-approximates $\mathrm{CSP}(\Gamma )$ with average sensitivity $O_{\Gamma }({\epsilon }^{-1}\log n)$ for all satisfiable instances; $\bullet$ or there exists ${\epsilon }_{\Gamma }\in (0,1]$ such that every algorithm that $(1-{\epsilon }_{\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.