Color Coding for the Sherrington-Kirkpatrick Model

@misc{harbuzova2026color,
  title = {{Color Coding for the Sherrington-Kirkpatrick Model}},
  author = {Alina Harbuzova and Saba Lepsveridze and Mahbod Majid and Ankur Moitra},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.10443},
  eprint = {2610.10443},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.10443},
}

TY  - UNPB
TI  - Color Coding for the Sherrington-Kirkpatrick Model
AU  - Alina Harbuzova
AU  - Saba Lepsveridze
AU  - Mahbod Majid
AU  - Ankur Moitra
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.10443
UR  - https://arxiv.org/abs/2610.10443
AB  - 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/ε, 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.
ER  -