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

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.