Chunyang Wang

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...