Abstract
We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $$4 \mathrm{e} p (D+1)^2\leq 1,$$ where $p$ is the maximum constraint violation probability and $D$ is the maximum dependency degree.
This condition is tight up to constant factors under $\mathbf{NP}\neq\mathbf{RP}$, matching known hardness bounds for counting and sampling in natural subclasses of CSPs. Our key ingredient is a novel $2$-tree expansion for constraint marginal probabilities that exhibits exponential decay of correlations throughout this regime.
This expansion yields deterministic polynomial-time approximate counting for fixed local parameters, randomized approximate counting with quadratic cost, and exact sampling in expected near-linear time when the local parameters are fixed.
Hongyang Liu
Ph.D. Student
I am a Ph.D. student in the Theory Group at the School of Computer Science, Nanjing University.
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.
Yitong Yin
Professor
I am a professor in the Theory Group at the School of Computer Science, Nanjing University. My research interests include randomized algorithms and computational sampling and counting, data structures and lower bounds, and parallel and distributed computing.
Can Zhou
Ph.D. Student
I am a Ph.D. student in the Theory Group at the School of Computer Science, Nanjing University, advised by Prof. Yitong Yin. My research interests include the algorithmic Lovász Local Lemma, counting and sampling algorithms, and theoretical parallel computing.