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 e p (D+1)2≤ 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 NP≠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.
Related
- A general counting and sampling Lovász local lemma
- A sampling Lovász Local Lemma
- The Lovász Local Lemma Is Sharp for the Hat Guessing Number
- A LOCAL PROOF OF LANGLANDS'S SECOND MAIN LEMMA FOR LOCAL EPSILON FACTORS OVER NONARCHIMEDEAN LOCAL FIELDS
- A LOCAL PROOF OF LANGLANDS'S FIRST MAIN LEMMA FOR LOCAL EPSILON FACTORS OVER NONARCHIMEDEAN LOCAL FIELDS
BibTeX
@misc{liu2026counting,
title = {{A Counting and Sampling Lovász Local Lemma}},
author = {Hongyang Liu and Chunyang Wang and Yitong Yin and Yiyao Zhang and Can Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.08616},
eprint = {2608.08616},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.08616},
}
RIS
TY - UNPB
TI - A Counting and Sampling Lovász Local Lemma
AU - Hongyang Liu
AU - Chunyang Wang
AU - Yitong Yin
AU - Yiyao Zhang
AU - Can Zhou
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2608.08616
UR - https://arxiv.org/abs/2608.08616
AB - 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 e p (D+1)^2≤ 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 NP≠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.
ER -