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
$\Phi$ when the width is logarithmic in the maximum degree. This closes an
exponential gap between the known upper and lower bounds.
  Moreover our algorithm extends straightforwardly to approximate sampling,
which shows that under Lov\'asz Local Lemma-like conditions it is not only
possible to find a satisfying assignment, it is also possible to generate one
approximately uniformly at random from the set of all satisfying assignments.
Our approach is a significant departure from earlier techniques in approximate
counting, and is based on a framework to bootstrap an oracle for computing
marginal probabilities on individual variables. Finally, we give an application
of our results to show that it is algorithmically possible to sample from the
posterior distribution in an interesting class of graphical models.
