A sampling Lovász Local Lemma
Abstract
We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy 4e p(Δ+1)2≤1, where p is the largest constraint-violation probability under the uniform product distribution, and Δ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou~\cite{CountingLLL} as a subroutine and returns a satisfying assignment sampled within total-variation distance ε of the uniform distribution in (n+m/ε)O(kΔlog D) time, where n and m are the numbers of variables and constraints, D is the common domain size, and k bounds the constraint arity. We also give an asymmetric product-form condition under which both counting and sampling are efficient. To supply the counts needed in the additional regime, we extend the marginal-expansion proof of Liu et al.
Related
- A Counting and Sampling Lovász Local Lemma
- A general counting and 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{achlioptas2026sampling,
title = {{A sampling Lovász Local Lemma}},
author = {Dimitris Achlioptas},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18712},
eprint = {2609.18712},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18712},
}
RIS
TY - UNPB
TI - A sampling Lovász Local Lemma
AU - Dimitris Achlioptas
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.18712
UR - https://arxiv.org/abs/2609.18712
AB - We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy 4e p(Δ+1)^2≤1, where p is the largest constraint-violation probability under the uniform product distribution, and Δ is the maximum degree of the dependency graph. The algorithm invokes the recent efficient approximate counting algorithm of Liu, Wang, Yin, Zhang, and Zhou~\cite{CountingLLL} as a subroutine and returns a satisfying assignment sampled within total-variation distance ε of the uniform distribution in (n+m/ε)^O(kΔlog D) time, where n and m are the numbers of variables and constraints, D is the common domain size, and k bounds the constraint arity. We also give an asymmetric product-form condition under which both counting and sampling are efficient. To supply the counts needed in the additional regime, we extend the marginal-expansion proof of Liu et al.
ER -