# Sampling Lov'asz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2022.

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

- [Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm](https://mlsanity.com/paper/2609.15268/) (2026)

## Abstract (arXiv)

We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has n variables with domain size at most q, each constraint contains at most k variables, shares variables with at most Delta constraints, and is violated with probability at most p by a uniform random assignment. The algorithm returns an almost uniform satisfying assignment in expected poly(q,k,Delta)·tildeO(n) time, as long as a local lemma condition is satisfied: [ k· p· q2· Delta5≤ C0quadfor a suitably small absolute constant C0. ] Previously, under similar local lemma conditions, sampling algorithms with running time polynomial in both n and Delta were only known for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations. The key term Delta5 in our local lemma condition also improves the previously best known Delta7 for general CSPs [JPV21b] and Delta5.714 for atomic CSPs, including the special case of k-CNF [JPV21a, HSW21]. Our sampling approach departs from previous fast algorithms for sampling LLL, which were based on Markov chains. A crucial step of our algorithm is a recursive marginal sampler that is of independent interests. Within a local lemma regime, this marginal sampler can draw a random value for a variable according to its marginal distribution, at a cost independent of the size of the CSP.