# A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 126 references that are in the map.
- First posted on arXiv 12 Jul 2025.

## Builds on (most cited first, 24 of 24)

- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [Another look at the Gardner problem](https://mlsanity.com/paper/1306.3979/) (2013)
- [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013)
- [Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems](https://mlsanity.com/paper/1511.05634/) (2015)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [Fully lifted random duality theory](https://mlsanity.com/paper/2312.00070/) (2023)
- [Upper-bounding ℓ1-optimization weak thresholds](https://mlsanity.com/paper/1303.7289/) (2013)
- [Algorithmic pure states for the negative spherical perceptron](https://mlsanity.com/paper/2010.15811/) (2020)
- [Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster](https://mlsanity.com/paper/2111.03084/) (2021)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Clustering of solutions in the symmetric binary perceptron](https://mlsanity.com/paper/1911.06756/) (2019)
- [Algorithms and Barriers in the Symmetric Binary Perceptron Model](https://mlsanity.com/paper/2203.15667/) (2022)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses](https://mlsanity.com/paper/2110.07847/) (2021)
- [Algorithmic Thresholds in Mean Field Spin Glasses](https://mlsanity.com/paper/2009.11481/) (2020)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [Lifted RDT based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networks](https://mlsanity.com/paper/2312.08257/) (2023)
- [Bounding ground state energy of Hopfield models](https://mlsanity.com/paper/1306.3764/) (2013)
- [The algorithmic hardness threshold for continuous random energy models](https://mlsanity.com/paper/1810.05129/) (2018)

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

- [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)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)
- [Precise sample covariance spectral norm error -- an RDT view](https://mlsanity.com/paper/2607.14460/) (2026)

## Abstract (arXiv)

We consider algorithmic determination of the n-dimensional Sherrington-Kirkpatrick (SK) spin glass model ground state free energy. It corresponds to a binary maximization of an indefinite quadratic form and under the worst case principles of the classical NP complexity theory it is hard to approximate within a log(n)const. factor. On the other hand, the SK's random nature allows (polynomial) spectral methods to typically approach the optimum within a constant factor. Naturally one is left with the fundamental question: can the residual (constant) computational gap be erased? Following the success of Controlled Loosening-up (CLuP) algorithms in planted models, we here devise a simple practical CLuP-SK algorithmic procedure for (non-planted) SK models. To analyze the typical success of the algorithm we associate to it (random) CLuP-SK models. Further connecting to recent random processes studies [94,97], we characterize the models and CLuP-SK algorithm via fully lifted random duality theory (fl RDT) [98]. Moreover, running the algorithm we demonstrate that its performance is in an excellent agrement with theoretical predictions. In particular, already for n on the order of a few thousands CLuP-SK achieves ~ 0.76 ground state free energy and remarkably closely approaches theoretical nrightarrow∞ limit ≈ 0.763. For all practical purposes, this renders computing SK model's near ground state free energy as a typically easy problem.