  The study of Markov processes and broadcasting on trees has deep connections
to a variety of areas including statistical physics, graphical models,
phylogenetic reconstruction, Markov Chain Monte Carlo, and community detection
in random graphs. Notably, the celebrated Belief Propagation (BP) algorithm
achieves Bayes-optimal performance for the reconstruction problem of predicting
the value of the Markov process at the root of the tree from its values at the
leaves.
  Recently, the analysis of low-degree polynomials has emerged as a valuable
tool for predicting computational-to-statistical gaps. In this work, we
investigate the performance of low-degree polynomials for the reconstruction
problem on trees. Perhaps surprisingly, we show that there are simple tree
models with $N$ leaves and bounded arity where (1) nontrivial reconstruction of
the root value is possible with a simple polynomial time algorithm and with
robustness to noise, but not with any polynomial of degree $N^{c}$ for $c > 0$
a constant depending only on the arity, and (2) when the tree is unknown and
given multiple samples with correlated root assignments, nontrivial
reconstruction of the root value is possible with a simple Statistical Query
algorithm but not with any polynomial of degree $N^c$. These results clarify
some of the limitations of low-degree polynomials vs. polynomial time
algorithms for Bayesian estimation problems. They also complement recent work
of Moitra, Mossel, and Sandon who studied the circuit complexity of Belief
Propagation. As a consequence of our main result, we show that for some $c' >
0$ depending only on the arity, $\exp(N^{c'})$ many samples are needed for RBF
kernel regression to obtain nontrivial correlation with the true regression
function (BP). We pose related open questions about low-degree polynomials and
the Kesten-Stigum threshold.
