Preprint
Aug 2026
A COUNTING AND SAMPLING LOVÁSZ LOCAL LEMMA
We establish counting and sampling analogues of the Lov\'asz Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $$4 \mathrm{e} p (D+1)^2\leq 1, $$ where $p$ is the maximum constrain...
Hong-Yang Liu, Chunyang Wang, Yi-Tong Yin et al.
· 0 citations