Approximate counting, the Lovasz local lemma, and inference in graphical models
In this paper we introduce a new approach for approximately 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 exponent...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Association for Computing Machinery (ACM)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116220 https://orcid.org/0000-0001-7047-0495 |