Abstract
We establish a counting analogue of the Lovász Local Lemma: we give polynomial-time algorithms for approximately counting satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $4 \mathrm{e}\cdot p\cdot (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, matching known lower bounds $pD^2\gtrsim 1$ for approximate counting in natural subclasses of CSPs. The core of our approach is a novel $2$-tree expansion for constraint marginal probabilities, which captures the decay of correlations in the local lemma regime.
Hongyang Liu
Reader
I am a PhD student in the Theory Group in the Department of Computer Science and Technology at 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 in the Department of Computer Science and Technology at Nanjing University. I am interested in Theoretical Computer Science.
Can Zhou
Graduate Student
I am a graduate student in the Theory Group in the Department of Computer Science and Technology at 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.