  In many natural average-case problems, there are or there are believed to be
critical values in the parameter space where the structure of the space of
solutions changes in a fundamental way. These phase transitions are often
believed to coincide with drastic changes in the computational complexity of
the associated problem.
  In this work, we study the circuit complexity of inference in the broadcast
tree model, which has important applications in phylogenetic reconstruction and
close connections to community detection. We establish a number of qualitative
connections between phase transitions and circuit complexity in this model.
Specifically, we show that there is a $\mathbf{TC}^0$ circuit that competes
with the Bayes optimal predictor in some range of parameters above the
Kesten-Stigum bound. We also show that there is a $16$ label broadcast tree
model beneath the Kesten-Stigum bound in which it is possible to accurately
guess the label of the root, but beating random guessing is
$\mathbf{NC}^1$-hard on average. The key to locating phase transitions is often
to study some intrinsic notions of complexity associated with belief
propagation \--- e.g. where do linear statistics fail, or when is the posterior
sensitive to noise? Ours is the first work to study the complexity of belief
propagation in a way that is grounded in circuit complexity.
