Before revision:  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;
After revision:  Our results include: (i) a conjecture about a precise criterion for when the problems of detection and recovery should be algorithmically tractable . At precisely the predicted tractable regime, we give: (i) a general polynomial-time algorithm for the problem of detection: distinguishing a graph with a planted signal from one without;