# Towards the sampling Lov'asz Local Lemma

arXiv: https://arxiv.org/abs/2011.12196 · HTML: https://mlsanity.com/paper/2011.12196/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2020.

## Built on by (most cited first, 3 of 3)

- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm](https://mlsanity.com/paper/2609.15268/) (2026)

## Abstract (arXiv)

Let Phi = (V, C) be a constraint satisfaction problem on variables v1,dots, vn such that each constraint depends on at most k variables and such that each variable assumes values in an alphabet of size at most [q]. Suppose that each constraint shares variables with at most Delta constraints and that each constraint is violated with probability at most p (under the product measure on its variables). We show that for k, q = O(1), there is a deterministic, polynomial time algorithm to approximately count the number of satisfying assignments and a randomized, polynomial time algorithm to sample from approximately the uniform distribution on satisfying assignments, provided that [C· q3· k · p · Delta7 < 1, quad where C  is an absolute constant.] Previously, a result of this form was known essentially only in the special case when each constraint is violated by exactly one assignment to its variables. For the special case of k-CNF formulas, the term Delta7 improves the previously best known Delta60 for deterministic algorithms [Moitra, J.ACM, 2019] and Delta13 for randomized algorithms [Feng et al., arXiv, 2020]. For the special case of properly q-coloring k-uniform hypergraphs, the term Delta7 improves the previously best known Delta14 for deterministic algorithms [Guo et al., SICOMP, 2019] and Delta9 for randomized algorithms [Feng et al., arXiv, 2020].