  Many statistical inference problems correspond to recovering the values of a
set of hidden variables from sparse observations on them. For instance, in a
planted constraint satisfaction problem such as planted 3-SAT, the clauses are
sparse observations from which the hidden assignment is to be recovered. In the
problem of community detection in a stochastic block model, the community
labels are hidden variables that are to be recovered from the edges of the
graph.
  Inspired by ideas from statistical physics, 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 statistical inference problems
that includes both community detection in stochastic block models, and all
planted 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. At
precisely the predicted tractable regime, we give:
  (i) a general polynomial-time algorithm for the problem of detection:
distinguishing an input with a planted signal from one without;
  (ii) a general polynomial-time algorithm for the problem of recovery:
outputting a vector that correlates with the hidden assignment significantly
better than a random guess would.
