Before revision:  Inspired by this, we investigate the predictions made by the cavity method for the algorithmic problemsof detecting and recovering a planted signal in a general model of sparse random graphs.
After revision:  Inspired by this, we investigate the predictions made by the cavity method for the presence of a stable fixed point for belief propogation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. In this work, we consider a general model of sparse random graphs.