{"id":"arxiv/2611.05446","url":"https://arxiv.org/abs/2611.05446","tags":["cs.DS","cond-mat.stat-mech","math.OC","math.PR","quant-ph"],"score":0,"title":"A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model","domain":"cs.DS","source":"arxiv","authors":["Dylan Herman","Shouvanik Chakrabarti","Junhyung Lyle Kim","Guneykan Ozgul"],"reviews":0,"subject":"cs.DS","summary":"Montanari's incremental approximate message passing (IAMP) algorithm [FOCS 2019; SIAM J. Comput., 2025] and the zero-temperature formulation of El Alaoui, Montanari and Sellke (AMS) [Ann. Probab., 2021] find a $(1-\\varepsilon)$ approximation to the maximum Sherrington-Kirkpatrick (SK) energy in $C(\\varepsilon)N^2$ operations for fixed accuracy, with probability tending to one as $N\\to\\infty$, under their respective full-support and access-model assumptions. However, it was unknown whether this approximation could be achieved with work polynomial in both $N$ and $1/\\varepsilon$, together with…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}