  We study the low-degree hardness of broadcasting on trees. Broadcasting on
trees has been extensively studied in statistical physics, in computational
biology in relation to phylogenetic reconstruction and in statistics and
computer science in the context of block model inference, and as a simple data
model for algorithms that may require depth for inference.
  The inference of the root can be carried by celebrated Belief Propagation
(BP) algorithm which achieves Bayes-optimal performance. Despite the fact that
this algorithm runs in linear time (using real operations), recent works
indicated that this algorithm in fact requires high level of complexity.
Moitra, Mossel and Sandon constructed a chain for which estimating the root
better than random (for a typical input) is $NC1$ complete. Kohler and Mossel
constructed chains such that for trees with $N$ leaves, recovering the root
better than random requires a polynomial of degree $N^{\Omega(1)}$. Both works
above asked if such complexity bounds hold in general below the celebrated {\em
Kesten-Stigum} bound.
  In this work, we prove that this is indeed the case for low degree
polynomials. We show that for the broadcast problem using any Markov chain on
trees with $n$ leaves, below the Kesten Stigum bound, any $O(\log n)$ degree
polynomial has vanishing correlation with the root.
  Our result is one of the first low-degree lower bound that is proved in a
setting that is not based or easily reduced to a product measure.
