{"ID":2895425,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.09247","arxiv_id":"2507.09247","title":"A CLuP algorithm to practically achieve $\\sim 0.76$ SK--model ground state free energy","abstract":"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 \\emph{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 \\emph{typically} approach the optimum within a constant factor. Naturally one is left with the fundamental question: can the residual (constant) \\emph{computational gap} be erased? Following the success of \\emph{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 \\emph{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 $\\sim 0.76$ ground state free energy and remarkably closely approaches theoretical $n\\rightarrow\\infty$ limit $\\approx 0.763$. For all practical purposes, this renders computing SK model's near ground state free energy as a \\emph{typically} easy problem.","short_abstract":"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 \\emph{worst case} principles of the classical NP complexity theory it is hard to approximate within a...","url_abs":"https://arxiv.org/abs/2507.09247","url_pdf":"https://arxiv.org/pdf/2507.09247v1","authors":"[\"Mihailo Stojnic\"]","published":"2025-07-12T10:58:50Z","proceeding":"cond-mat.dis-nn","tasks":"[\"cond-mat.dis-nn\",\"cs.IT\",\"math.OC\",\"stat.ML\"]","methods":"[]","has_code":false}