An $\widetilde{O}\left(n^2 \right)$-Time Sampler for Zero-Field Ferromagnetic Ising Models
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.26197
curl -X POST /api/v1/records/arxiv/2609.26197/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.26197/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'