  We prove an algorithmic hardness result for finding low-energy states in the
so-called \emph{continuous random energy model (CREM)}, introduced by Bovier
and Kurkova in 2004 as an extension of Derrida's \emph{generalized random
energy model}. The CREM is a model of a random energy 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 \emph{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 \in \{0,1\}^N$
with $X_v \ge (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 $X_v \ge (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.
