A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model
cs.DS, cond-mat.stat-mech, math.OC, math.PR, quant-ph
Submitted: 2026-11-03
Updated: 2026-11-03
Terminology
Sources
- Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling
- Parisi formula for the ground state energy in the mixed p-spin model
- Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm
- Disorder chaos and multiple valleys in spin glasses
- FRSB in the SK spin glass: convergence to full-interval support at zero temperature
- On the energy landscape of the mixed even $p$-spin model
- Algorithmic Thresholds in Mean Field Spin Glasses
- Optimization of Mean-field Spin Glasses
- A unifying tutorial on Approximate Message Passing
- The Thermodynamic Limit in Mean Field Spin Glass Models
- Entrywise dynamics and universality of general first order methods
- Semidefinite programs simulate approximate message passing robustly
- Fast, robust approximate message passing
- Potential Hessian Ascent: The Sherrington-Kirkpatrick Model
- A Dynamic Programming Approach to the Parisi Functional
- A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models
- Optimization of the Sherrington-Kirkpatrick Hamiltonian
- An Introduction to Matrix Concentration Inequalities
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time