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\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.
Chunyang Wang
Postdoc
I am Chunyang Wang (王淳扬), currently a project researcher (postdoc) at the National Institute of Informatics (NII), hosted by Prof. Yuichi Yoshida. My research interests broadly lie in theoretical computer science, especially algorithms for counting and sampling and algorithmic stability.
Yuichi Yoshida
Professor
I am a professor in the Principles of Informatics Research Division at the National Institute of Informatics. My research spans sublinear-time testing, approximation algorithms, constraint satisfaction problems, spectral graph theory, algorithmic stability, and theory-inspired practical algorithms for real-world graphs.