# The algorithmic hardness threshold for continuous random energy models

### Louigi Addario-Berry

McGill University, Montreal, Canada### Pascal Maillard

Université de Toulouse, France

## Abstract

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 randomenergy landscape $(X_{v})_{v∈{0,1}_{N}}$ 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 $ε>0$ a linear-time algorithm which finds states $v∈{0,1}_{N}$ with $X_{v}≥(x_{∗}−ε)N$. Second, we show that the value $x_{∗}$ is essentially best-possible: for any $ε>0$, any algorithm which finds states $v$ with $X_{v}≥(x_{∗}+ε)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.

## Cite this article

Louigi Addario-Berry, Pascal Maillard, The algorithmic hardness threshold for continuous random energy models. Math. Stat. Learn. 2 (2019), no. 1, pp. 77–101

DOI 10.4171/MSL/12