  In recent times the cavity method, a statistical physics-inspired heuristic,
has been successful in conjecturing computational thresholds that have been
rigorously confirmed -- such as for community detection in the sparse regime of
the stochastic block model. Inspired by this, we investigate the predictions
made by the cavity method for the algorithmic problems of detecting and
recovering a planted signal in a general model of sparse random graphs. The
model we study generalizes the well-understood case of the stochastic block
model, the less well understood case of random constraint satisfaction problems
with planted assignments, as well as "semi-supervised" variants of these
models. Our results include: (i) a conjecture about a precise criterion for
when the problems of detection and recovery should be algorithmically tractable
arising from a heuristic analysis of when a particular fixed point of the
belief propagation algorithm is stable; (ii) a rigorous polynomial-time
algorithm for the problem of detection: distinguishing a graph with a planted
signal from one without; (iii) a rigorous polynomial-time algorithm for the
problem of recovery: outputting a vector that correlates with the planted
signal significantly better than a random guess would.
  The rigorous algorithms are based on the spectra of matrices that arise as
the derivatives of the belief propagation update rule. An interesting
unanswered question raised is that of obtaining evidence of computational
hardness for convex relaxations whenever hardness is predicted by the cavity
method.
