A Counting and Sampling Lovász Local Lemma

Hongyang Liu, Chunyang Wang, Yitong Yin +2

We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of gener…