Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models
Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models
In this article, we introduce a new approach to approximate counting in bounded degree systems with higher-order constraints. Our main result is an algorithm to approximately count the number of solutions to a CNF formula Φ when the width is logarithmic in the maximum degree. This closes an exponential gap …