A Counting and Sampling Lovász Local Lemma

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.

Publication
Preprint
Hongyang Liu
Hongyang Liu
Postdoctoral Fellow

I am a Postdoctoral Fellow in the School of Computing and Data Science at The University of Hong Kong, working with Prof. Weiming Feng. Previously, I received my Ph.D. in theoretical computer science from Nanjing University, advised by Prof. Yitong Yin. My research interests include parallel algorithms, local and distributed algorithms, and sampling and counting algorithms.

Chunyang Wang
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
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.

Yiyao Zhang
Ph.D. Student

I am a third-year Ph.D. student in the Theory Group at the School of Computer Science, Nanjing University, advised by Prof. Yitong Yin. My research interests include sampling and counting, learning theory, and probability theory.

Can Zhou
Can Zhou
Ph.D. 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 probabilistic methods, counting and sampling algorithms, and the algorithmic Lovász Local Lemma.