Before revision:  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;
After revision:  The model we study generalizes the well-understood case of the stochastic block model, the less well understood case of random constraint satisfaction problems as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where 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;