We present algorithms for approximate counting and sampling of spin models on graphs with low threshold rank or large girth. For an $n$‑vertex graph $G$, let $k_\eta(G)$ denote the number of normalized‑Laplacian eigenvalues strictly below $\eta$.
An $\varepsilon$‑approximate counting algorithm returns an estimate $\widehat Z$ satisfying $(1-\varepsilon)Z\le \widehat Z\le(1+\varepsilon)Z$ with probability at least $3/4$. An $\varepsilon$‑approximate sampling algorithm produces a configuration whose distribution is within total variation distance $\varepsilon$ of the target distribution.
Main results
(a) Ferromagnetic Potts. Fix $q\ge2$ and $\eta\in(0,1]$. There exists $\beta_0(q,\eta)$ such that for every inverse temperature $\beta\ge\beta_0$, the zero‑field $q$‑state Potts model admits approximate counting and sampling:
- On arbitrary graphs in time $\exp(O(k_\eta))\operatorname{poly}(n,1/\varepsilon)$;
- For any $\Delta\ge3$, on $\Delta$‑regular graphs of girth $g$ in time $\exp(O(n e^{-g}))\operatorname{poly}(n,1/\varepsilon)$.
(b) Bipartite hard‑core. Fix $\Delta\ge3$ and $\eta\in(0,1]$. There exists $\lambda_0(\Delta,\eta)$ such that for every fugacity $\lambda\ge\lambda_0$, the hard‑core model admits approximate counting and sampling:
- On $\Delta$‑regular vertex‑transitive bipartite graphs in time $\exp(O(k_\eta))\operatorname{poly}(n,1/\varepsilon)$;
- On $\Delta$‑regular bipartite graphs of girth $g$ in time $\exp(O(n e^{-g}))\operatorname{poly}(n,1/\varepsilon)$.
All four statements follow from verifying the hypotheses of a new framework called C‑3PO. At a high level, C‑3PO enumerates small cuts and reconstructs the original measure via cluster expansions, while an active‑regression technique improves subspace enumeration.
Review