Open Research Index

Color Coding for the Sherrington-Kirkpatrick Model

Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra

arXivarxiv/2610.10443Oct 7, 2026cs.DSscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.10443
curl -X POST /api/v1/records/arxiv/2610.10443/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.10443/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'