# A Sampling Lov'asz Local Lemma for Large Domain Sizes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2023.

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

- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [One-Shot Learning for k-SAT](https://mlsanity.com/paper/2502.07135/) (2025)

## Abstract (arXiv)

We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime:  pD2+oq(1)lesssim 1.  When the domain size q of each variable becomes sufficiently large, this almost matches the known lower bound pD2gtrsim 1 for approximate counting and sampling solutions to atomic CSPs [Bez'akov'a et al, SICOMP '19; Galanis, Guo, Wang, TOCT '22], thus establishing an almost tight sampling Lov'asz local lemma for large domain sizes.