Fast mixing of Glauber dynamics for the SK model up to β = 1
For $J \in \mathbb{R}^{n \times n}$ and $h \in \mathbb{R}^n$ let $\mu_{J,h}(x) \propto \exp\bigl(\frac12 x^{\mathsf T} J x + h^{\mathsf T} x\bigr)$ on $\{\pm1\}^n$. In the Sherrington–Kirkpatrick model $J = \beta W$ with $W \sim \mathrm{GOE}(n)$, normalised so that its off-diagonal entries have variance $1/n$, and statements hold with high probability over $W$. Glauber dynamics mixes in $O(n^2)$ time for $\beta < \frac14$ (Eldan, Koehler and Zeitouni) and in $O(n \log n)$ time for $\beta < 0.295$ (Anari, Koehler and Vuong). Without an external field, a different sampler based on stochastic localization works in Wasserstein distance for $\beta < \frac12$ (El Alaoui, Montanari and Sellke), and by Celentano's work for all $\beta < 1$; no stable algorithm samples for $\beta > 1$.
Problem. Consider the SK model with an arbitrary external field. Does Glauber dynamics mix fast, meaning in polynomial time, up to the replica-symmetry-breaking threshold $\beta_* = 1$?
Source: Rödder, Open Problem 15 of Randomstrasse101, in “Sampling from the Sherrington-Kirkpatrick Model” (2024); Entry 7 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- PR — Probability
- Secondary
- MP
- Keywords
- Glauber dynamics, mixing time, Randomstrasse101, Sherrington–Kirkpatrick model, spin glasses
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@article{eldan2022spectral,
author = {Eldan, Ronen and Koehler, Frederic and Zeitouni, Ofer},
title = {A spectral condition for spectral gap: fast mixing in high-temperature {I}sing models},
journal = {Probability Theory and Related Fields},
volume = {182},
number = {3},
pages = {1035--1051},
year = {2022}
}
@inproceedings{anari2024trickle,
author = {Anari, Nima and Koehler, Frederic and Vuong, Thuy-Duong},
title = {Trickle-down in localization schemes and applications},
booktitle = {Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)},
pages = {1094--1105},
year = {2024}
}
@inproceedings{elalaoui2022sampling,
author = {El Alaoui, Ahmed and Montanari, Andrea and Sellke, Mark},
title = {Sampling from the {S}herrington--{K}irkpatrick {G}ibbs measure via algorithmic stochastic localization},
booktitle = {63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022)},
pages = {323--334},
year = {2022}
}
@article{celentano2024sudakov,
author = {Celentano, Michael},
title = {{S}udakov--{F}ernique post-{AMP}, and a new proof of the local convexity of the {TAP} free energy},
journal = {The Annals of Probability},
volume = {52},
number = {3},
pages = {923--954},
year = {2024}
}
Resolution claims
We prove worst-case total-variation cutoff for the zero-field Gaussian Sherrington--Kirkpatrick heat-bath dynamics at every fixed inverse temperature \(0\leq\beta<1\). With rate-one refresh at each spin, the cutoff location is \(\log n/(2\lambda(\beta))\) for a positive deterministic rate \(\lambda(\beta)\). The location for uniformly chosen single-site update attempts is \(n\) times as large. Convergence is in probability over the disorder.
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-09 | Open → Partially resolved | The registry's curators | Cutoff throughout the high-temperature Sherrington–Kirkpatrick phase v1 recorded from math @ fd4aeeb, build/paper.tex. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00033, "Fast mixing of Glauber dynamics for the SK model up to β = 1", clopen.solutions.