Near-linear-Time Sampling of the Ferromagnetic Ising Model at the Tree Uniqueness Threshold
We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself. The method also gives sampling algorithms for the XY and integer Potts models. On an $n$-vertex graph with $m$ edges and maximum degree at most $\Delta$, we obtain the f...