**
Counting without sampling. New algorithms for enumeration problems using
statistical physics
**

**Abstract :** We propose a new type of approximate counting algorithms for the problems of enumerating the
number of independent sets and proper colorings in low degree graphs with large girth. Our algorithms are
not based on a commonly used Markov chain technique, but rather are
inspired by recent
developments in statistical physics in connection with correlation decay properties of Gibbs measures and its implications to
uniqueness of Gibbs measures on infinite trees, reconstruction problems and local weak convergence methods.
On a negative side, our algorithms provide $\epsilon$-approximations only to the
logarithms of the size of a feasible set (also known as free energy in statistical physics).
But on the positive side,
unlike Markov chain based algorithms, our approach provides deterministic as opposed to probabilistic guarantee on
approximations. Moreover, for some regular graphs we obtain explicit values for
the counting problem. For example, we show that every $4$-regular $n$-node graph
with large girth has asymptotically $(1.494\ldots)^n$ independent
sets, and in every $r$-regular graph with $n$ nodes and large girth
the number of $q\geq r+1$-proper colorings is asymptotically
$(q(1-{1\over q})^{r\over 2})^n$, for large $n$. In statistical physics terminology, we
compute explicitly the partition function (free energy)
in these cases. We extend our results to random regular graphs graphs also.
The explicit results obtained in this paper would be hard to derive via Markov chain sampling technique.

[Joint work with David Gamarnik]