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\le 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}\ne \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.

arXiv commentV1 was titled "A Counting Lovász Local Lemma". V2 adds an exact sampler with expected near-linear running time under the same LLL condition. V3 substantially simplifies the construction of the near-linear time exact sampler