# Approximate Counting for Spin Systems in Sub-Quadratic Time

arXiv: https://arxiv.org/abs/2306.14867 · HTML: https://mlsanity.com/paper/2306.14867/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2023.

## Built on by (most cited first, 1 of 1)

- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)

## Abstract (arXiv)

We present two randomised approximate counting algorithms with widetildeO(n2-c/varepsilon2) running time for some constant c>0 and accuracy varepsilon: (1) for the hard-core model with fugacity λ on graphs with maximum degree Delta when λ=O(Delta-1.5-c1) where c1=c/(2-2c); (2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as mathbbZ2. 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 λ = o(Delta-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 mathbbZd, but with a running time of the form widetildeOleft(n2varepsilon-2/2^c(log n)1/dright) where d is the exponent of the polynomial growth and c>0 is some constant.