Approximate Counting for Spin Systems in Sub-Quadratic Time

Abstract

We present two randomised approximate counting algorithms with $\tilde{O}(n^{2-c}/{\epsilon }^2)$ running time for some constant $c>0$ and accuracy $\epsilon$: (1) for the hard-core model with fugacity $\hat{I}»$ on graphs with maximum degree $\hat{I}”$ when $\hat{I}»=O(\hat{I}{”}^{-1.5-c_1})$ where $c_1=c/(2-2c)$; (2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as ${\mathbb{Z}}^2$. For the hard-core model, Weitz's algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when $\hat{I}»=o(\hat{I}{”}^{-2})$. Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as ${\mathbb{Z}}^d$, but with a running time of the form $\tilde{O}\left(n^2{\epsilon }^{-2}/2^{c(\log n{)}^{1/d}}\right)$ where $d$ is the exponent of the polynomial growth and $c>0$ is some constant.

27 pages. This is the TheoretiCS journal version