Polynomial time algorithm improves partition function approximation in spin glass models
Color Coding for the Sherrington-Kirkpatrick Model
Data Structures and Algorithms
Summary
Approximating certain mathematical functions that describe complex systems like spin glasses can be very hard and slow. The authors present a new algorithm that does this approximation much faster and with guaranteed accuracy. Their method relies on a clever use of color coding combined with previous work on mathematical properties of these systems. This makes it possible to handle larger problems in models like the Sherrington-Kirkpatrick spin glass, which helps understand complex disorder in physics.
What this means in practice
- •For statistical physicists: Calculate partition functions more efficiently to study phase transitions in disordered physical systems.
- •For machine learning engineers: Improve algorithms relying on spin glass models by enabling faster and more accurate evaluations of their key functions.
Authors
Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra
Abstract
We give a polynomial-time algorithm for approximating the partition function of mean-field mixed $p$-spin models to arbitrarily high accuracy throughout the second-moment regime. This improves the quasipolynomial-time algorithm of Bencs, Huang, Lee, Liu, and Regts (arXiv:2507.15616) and answers their open question. In particular, our result covers the entire replica-symmetric regime of the Sherrington--Kirkpatrick model. The algorithm is deterministic, runs in time polynomial in $n$ and $1/\varepsilon$, and succeeds for every typical realization of the disorder. Our main technical contribution is a new algorithmic application of color coding to the classical high-temperature expansion introduced by Aizenman, Lebowitz, and Ruelle in their study of fluctuations of the Sherrington--Kirkpatrick partition function. We combine this approach with the zero-freeness established by Bencs et al. (arXiv:2507.15616) to convert additive approximations into multiplicative ones.