A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model
Abstract
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−ε) approximation to the maximum Sherrington-Kirkpatrick (SK) energy in C(ε)N2 operations for fixed accuracy, with probability tending to one as N→∞, 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/ε, together with quantitative guarantees at finite dimension. Under the same assumptions as AMS, we introduce grouped IAMP with exact Gaussian query outputs (GEG-IAMP), which is the first SK approximation algorithm with total work polynomial in N and 1/ε and a finite-size guarantee above a dimension threshold polynomial in 1/ε and log(1/α). More precisely, for every α∈(0,1/2), it returns a (1−ε) approximation with probability at least 1−α whenever N≥ Kε−2log2(e/ε)log(K/α), using O(N2/ε) work and O(N2) storage. GEG-IAMP replaces the Onsager correction by Reeves's coupling construction [arXiv:2508.10782] and groups Euler-Maruyama steps into O(1/ε) matrix-vector products. We also prove a relative guarantee for AMS IAMP with O(N2ε−3log2(e/ε)) work but a sufficient dimension exponential in inverse accuracy. By returning a fixed configuration below its dimension threshold, GEG-IAMP also provides an asymptotic fully polynomial randomized approximation scheme (AFPRAS), with an additive error independent of dimension.
Related
- An Autonomous Spectral Representation for Fully Asymmetric Spherical Sherrington-Kirkpatrick Dynamics
- A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
- Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model
- Sampling from the Sherrington-Kirkpatrick Model up to Criticality
- Free energy and fluctuations of generalized bipartite Sherrington-Kirkpatrick models and generalized Hopfield models
BibTeX
@misc{herman2026fully,
title = {{A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model}},
author = {Dylan Herman and Shouvanik Chakrabarti and Junhyung Lyle Kim and Guneykan Ozgul},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05446},
eprint = {2611.05446},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05446},
}
RIS
TY - UNPB
TI - A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model
AU - Dylan Herman
AU - Shouvanik Chakrabarti
AU - Junhyung Lyle Kim
AU - Guneykan Ozgul
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05446
UR - https://arxiv.org/abs/2611.05446
AB - 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−ε) approximation to the maximum Sherrington-Kirkpatrick (SK) energy in C(ε)N^2 operations for fixed accuracy, with probability tending to one as N→∞, 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/ε, together with quantitative guarantees at finite dimension. Under the same assumptions as AMS, we introduce grouped IAMP with exact Gaussian query outputs (GEG-IAMP), which is the first SK approximation algorithm with total work polynomial in N and 1/ε and a finite-size guarantee above a dimension threshold polynomial in 1/ε and log(1/α). More precisely, for every α∈(0,1/2), it returns a (1−ε) approximation with probability at least 1−α whenever N≥ Kε^−2log^2(e/ε)log(K/α), using O(N^2/ε) work and O(N^2) storage. GEG-IAMP replaces the Onsager correction by Reeves's coupling construction [arXiv:2508.10782] and groups Euler-Maruyama steps into O(1/ε) matrix-vector products. We also prove a relative guarantee for AMS IAMP with O(N^2ε^−3log^2(e/ε)) work but a sufficient dimension exponential in inverse accuracy. By returning a fixed configuration below its dimension threshold, GEG-IAMP also provides an asymptotic fully polynomial randomized approximation scheme (AFPRAS), with an additive error independent of dimension.
ER -