The algorithmic hardness threshold for continuous random energy models

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\in \{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]\to [0,1]$, which encodes the correlations between states.

We exhibit an algorithmic hardness threshold $x_{\ast }$, 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 $\epsilon >0$ a linear-time algorithm which finds states $v\in \{0,1{\}}^N$ with $X_v\ge (x_{\ast }-\epsilon )N$. Second, we show that the value $x_{\ast }$ is essentially best-possible: for any $\epsilon >0$, any algorithm which finds states $v$ with $X_v\ge (x_{\ast }+\epsilon )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.