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 ideas from statistical physics, the algorithmic problemsof detecting and recovering a planted signal in a general model of sparse random graphs.