A general counting and sampling Lovász local lemma
Abstract
Consider a constraint satisfaction problem C on finitely many independent random variables with dependency graph G. Let pa be the violation probability of a constraint a∈ C and NG2 (a) the set of constraints at distance one or two from a in G. Suppose that, there exists x∈ (0,1)C such that, for a sufficiently small universal constant c > 0, and for all a ∈ C, pa ≤ c · xa ∏b∈ NG2(a)(1−xb). Under the above analog of the asymmetric Lovász Local Lemma, we give an FPRAS for the probability that all constraints are satisfied, and an approximate sampler, running in polynomial expected time, for the product distribution conditioned on this event. The degree of the polynomial in the running time is independent of the domain sizes, constraint sizes, or degree of the dependency graph. Up to the choice of the constant c, our condition on pa matches known hardness results. Our work builds on the method of Liu, Wang, Yin, Zhang, and Zhou, who obtained an FPRAS for the probability of satisfaction in the setting of the symmetric Lovász Local Lemma. Our sampling result is new even in this special case.
Related
- A 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{jain2026general,
title = {{A general counting and sampling Lovász local lemma}},
author = {Vishesh Jain and Clayton Mizgerd and Huy Tuan Pham},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23671},
eprint = {2609.23671},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23671},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A general counting and sampling Lovász local lemma
AU - Vishesh Jain
AU - Clayton Mizgerd
AU - Huy Tuan Pham
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23671
UR - https://arxiv.org/abs/2609.23671
AB - Consider a constraint satisfaction problem C on finitely many independent random variables with dependency graph G. Let p_a be the violation probability of a constraint a∈ C and N_G^2 (a) the set of constraints at distance one or two from a in G. Suppose that, there exists x∈ (0,1)^C such that, for a sufficiently small universal constant c > 0, and for all a ∈ C, p_a ≤ c · x_a ∏_b∈ N_G^2(a)(1−x_b). Under the above analog of the asymmetric Lovász Local Lemma, we give an FPRAS for the probability that all constraints are satisfied, and an approximate sampler, running in polynomial expected time, for the product distribution conditioned on this event. The degree of the polynomial in the running time is independent of the domain sizes, constraint sizes, or degree of the dependency graph. Up to the choice of the constant c, our condition on p_a matches known hardness results. Our work builds on the method of Liu, Wang, Yin, Zhang, and Zhou, who obtained an FPRAS for the probability of satisfaction in the setting of the symmetric Lovász Local Lemma. Our sampling result is new even in this special case.
ER -