A Sampling Lov'asz Local Lemma for Large Domain Sizes
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). First posted on arXiv 27 Jul 2023.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2025: 2.
2 papers.
- 2025Learning CNF formulas from uniform random solutions in the local lemma regimecited by 2
- 2025One-Shot Learning for k-SATcited by 0
- 2025Learning CNF formulas from uniform random solutions in the local lemma regime4 Nov 2025
- 2025One-Shot Learning for k-SAT10 Feb 2025