A COUNTING AND SAMPLING LOVÁSZ LOCAL LEMMA

Abstract

We establish counting and sampling analogues of the Lov\'asz 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.