  Disordered systems such as spin glasses have been used extensively as models
for high-dimensional random landscapes and studied from the perspective of
optimization algorithms. In a recent paper by L. Addario-Berry and the second
author, the continuous random energy model (CREM) was proposed as a simple toy
model to study the efficiency of such algorithms. The following question was
raised in that paper: what is the threshold $\beta_G$, at which sampling
(approximately) from the Gibbs measure at inverse temperature $\beta$ becomes
algorithmically hard?
  This paper is a first step towards answering this question. We consider the
branching random walk, a time-homogeneous version of the continuous random
energy model. We show that a simple greedy search on a renormalized tree yields
a linear-time algorithm which approximately samples from the Gibbs measure, for
every $\beta < \beta_c$, the (static) critical point. More precisely, we show
that for every $\varepsilon>0$, there exists such an algorithm such that the
specific relative entropy between the law sampled by the algorithm and the
Gibbs measure of inverse temperature $\beta$ is less than $\varepsilon$ with
high probability.
  In the supercritical regime $\beta > \beta_c$, we provide the following
hardness result. Under a mild regularity condition, for every $\delta > 0$,
there exists $z>0$ such that the running time of any given algorithm
approximating the Gibbs measure stochastically dominates a geometric random
variable with parameter $e^{-z\sqrt{N}}$ on an event with probability at least
$1-\delta$.
