2026-06-09
On zeros and algorithms for disordered systems: Mean-field spin glasses
Publication
Publication
Presented at the
STOC '26: 58th Annual ACM Symposium on Theory of Computing (June 2026), Salt Lake City, USA
Spin glasses are fundamental probability distributions at the core of statistical physics, the theory of average-case computational complexity, and modern high-dimensional statistical inference. In the mean-field setting, we design deterministic quasipolynomial-time algorithms for estimating the partition function to arbitrarily high accuracy for all inverse temperatures in the second moment regime. In particular, for the Sherrington - Kirkpatrick model, our algorithms succeed for the entire replica-symmetric phase. To achieve this, we study the locations of the zeros of the partition function. Notably, our methods are conceptually simple, and apply equally well to the spherical case and the case of Ising spins.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1145/3798129.3800769 | |
| STOC '26: 58th Annual ACM Symposium on Theory of Computing | |
| creativecommons.org/licenses/by/4.0/ | |
| Organisation | Networks and Optimization |
|
Bencs, F., Huang, B., Lee, D. Z., Liu, K.& Regts, G. (2026). On zeros and algorithms for disordered systems: Mean-field spin glasses. Proceedings of the Annual ACM Symposium on Theory of Computing, 508–517.https://doi.org/10.1145/3798129.3800769 |
|
