{"id":"arxiv/2610.10443","url":"https://arxiv.org/abs/2610.10443","tags":["cs.DS","math-ph"],"score":0,"title":"Color Coding for the Sherrington-Kirkpatrick Model","domain":"cs.DS","source":"arxiv","authors":["Alina Harbuzova","Saba Lepsveridze","Mahbod Majid","Ankur Moitra"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}