An $\tilde{O}\left(n^2\right)$-Time Sampler for Zero-Field Ferromagnetic Ising Models

Abstract

We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time $\tilde{O}(m+n)+{\tilde{O}}_{\beta }(n^2{\log }^2(1/\epsilon ))$, where $n$ and $m$ are the numbers of vertices and edges, respectively, and $\epsilon$ is the approximation error. Our approach combines Benczúr--Karger cut sparsification with a new mixing time analysis of the Glauber dynamics for the random-cluster model. The mixing time analysis features a new monotone edge-count Poincaré inequality.

arXiv comment17 pages