# The algorithmic hardness threshold for continuous random energy models

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

## Key facts

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

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

- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025)

## Abstract (arXiv)

We prove an algorithmic hardness result for finding low-energy states in the so-called continuous random energy model (CREM), introduced by Bovier and Kurkova in 2004 as an extension of Derrida's generalized random energy model. The CREM is a model of a random energy landscape (Xv)_v ∈ 0,1N on the discrete hypercube with built-in hierarchical structure, and can be regarded as a toy model for strongly correlated random energy landscapes such as the family of p-spin models including the Sherrington--Kirkpatrick model. The CREM is parameterized by an increasing function A:[0,1]→[0,1], which encodes the correlations between states. We exhibit an algorithmic hardness threshold x_*, which is explicit in terms of A. More precisely, we obtain two results: First, we show that a renormalization procedure combined with a greedy search yields for any varepsilon > 0 a linear-time algorithm which finds states v ∈ 0,1N with Xv ≥ (x_*-varepsilon) N. Second, we show that the value x_* is essentially best-possible: for any varepsilon > 0, any algorithm which finds states v with Xv ≥ (x_*+varepsilon)N requires exponentially many queries in expectation and with high probability. We further discuss what insights this study yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.