# Optimization of the Sherrington-Kirkpatrick Hamiltonian

arXiv: https://arxiv.org/abs/1812.10897 · HTML: https://mlsanity.com/paper/1812.10897/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2018.

## Built on by (most cited first, 20 of 20)

- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Injectivity of ReLU networks: perspectives from statistical physics](https://mlsanity.com/paper/2302.14112/) (2023)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks](https://mlsanity.com/paper/2410.06717/) (2024)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [Fast, robust approximate message passing](https://mlsanity.com/paper/2411.02764/) (2024)
- [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Random Function Descent](https://mlsanity.com/paper/2305.01377/) (2023)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Quality-diversity in dissimilarity spaces](https://mlsanity.com/paper/2211.12337/) (2022)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view](https://mlsanity.com/paper/2506.18279/) (2025)
- [Phase retrieval with rank d measurements -- descending algorithms phase transitions](https://mlsanity.com/paper/2506.18282/) (2025)
- [Perfect reconstruction of sparse signals using nonconvexity control and one-step RSB message passing](https://mlsanity.com/paper/2512.17426/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)
- [Local-Minima-Preserving Continuous Relaxation of Ising Problems](https://mlsanity.com/paper/2606.30333/) (2026)

## Abstract (arXiv)

Let boldsymbol A∈mathbb Rn× n be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing langleboldsymbol σ,boldsymbol Aboldsymbol σrangle over binary vectors boldsymbol σ∈+1,-1n. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any varepsilon>0, outputs boldsymbol σ_*∈-1,+1n such that langleboldsymbol σ_*,boldsymbol Aboldsymbol σ_*rangle is at least (1-varepsilon) of the optimum value, with probability converging to one as n→∞. The algorithm's time complexity is C(varepsilon), n2. It is a message-passing algorithm, but the specific structure of its update rules is new. As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the Thouless-Anderson-Palmer equations.