  The continuous random energy model (CREM) is a toy model of disordered
systems introduced by Bovier and Kurkova in 2004 based on previous work by
Derrida and Spohn in the 80s. In a recent paper by Addario-Berry and Maillard,
they raised the following question: what is the threshold $\beta_G$, at which
sampling approximately the Gibbs measure at any inverse temperature
$\beta>\beta_G$ becomes algorithmically hard? Here, sampling approximately
means that the Kullback--Leibler divergence from the output law of the
algorithm to the Gibbs measure is of order $o(N)$ with probability approaching
$1$, as $N\rightarrow\infty$, and algorithmically hard means that the running
time, the numbers of vertices queries by the algorithms, is beyond of
polynomial order.
  The present work shows that when the covariance function $A$ of the CREM is
concave, for all $\beta>0$, a recursive sampling algorithm on a renormalized
tree approximates the Gibbs measure with running time of order
$O(N^{1+\varepsilon})$. For $A$ non-concave, the present work exhibits a
threshold $\beta_G<\infty$ such that the following hardness transition occurs:
a) For every $\beta\leq \beta_G$, the recursive sampling algorithm approximates
the Gibbs measure with running time of order $O(N^{1+\varepsilon})$. b) For
every $\beta>\beta_G$, a hardness result is established for a large class of
algorithms. Namely, for any algorithm from this class that samples the Gibbs
measure approximately, there exists $z>0$ such that the running time of this
algorithm is at least $e^{zN}$ with probability approaching $1$. In other
words, it is impossible to sample approximately in polynomial-time the Gibbs
measure in this regime.
  Additionally, we provide a lower bound of the free energy of the CREM that
could hold its own value.
