{"id":"arxiv/2609.26197","url":"https://arxiv.org/abs/2609.26197","tags":["cs.DS","math.PR"],"score":0,"title":"An $\\widetilde{O}\\left(n^2 \\right)$-Time Sampler for Zero-Field Ferromagnetic Ising Models","domain":"cs.DS","source":"arxiv","authors":["Weiming Feng","Heng Guo","Yiyao Zhang"],"reviews":0,"subject":"cs.DS","summary":"We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time $\\widetilde O(m+n)+\\widetilde O_β(n^2\\log^2 (1 / \\varepsilon))$, where $n$ and $m$ are the numbers of vertices and edges, respectively, and $\\varepsilon$ 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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-13","reactions":{}}