PreprintarXiv licencearXiv
An Õ(n2 )-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 Õ(m+n)+Õβ(n2log2 (1 / ε)), where n and m are the numbers of vertices and edges, respectively, and ε 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.
Related
- Critical and near-critical influence bounds for ferromagnetic Ising models
- Long-Time Behavior of Zero-Noise Mean-Field Adam
- Phase transition in the antiferromagnetic Ising model with external field
- Droplets obstruct Onsager-type solutions of the Ising model in a magnetic field
- Detailed balance and phase transition in Nash equilibria of mean-field Ising game
BibTeX
@misc{feng2026time,
title = {{An $\widetildeO\left(n^2 \right)$-Time Sampler for Zero-Field Ferromagnetic Ising Models}},
author = {Weiming Feng and Heng Guo and Yiyao Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26197},
eprint = {2609.26197},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26197},
}
RIS
TY - UNPB
TI - An Õ(n^2 )-Time Sampler for Zero-Field Ferromagnetic Ising Models
AU - Weiming Feng
AU - Heng Guo
AU - Yiyao Zhang
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.26197
UR - https://arxiv.org/abs/2609.26197
AB - We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time Õ(m+n)+Õ_β(n^2log^2 (1 / ε)), where n and m are the numbers of vertices and edges, respectively, and ε 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.
ER -