Preprint
Oct 2026
Color Coding for the Sherrington-Kirkpatrick Model
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...
Alina Harbuzova, Saba Lepsveridze, Mahbod Majid et al.
· 0 citations