Consider a rooted d-regular tree with \ell layers, where each vertex is colored either blue or green. Starting from the root, the color propagates down the tree so that each child inherits its parent’s color but flips with probability 30%. Now, suppose you only observe the colors of the leaves—can you infer the color of the root?

This setting describes a broadcasting process on trees, where in general we have q possible 'colors' and a transition matrix specifying the probability that a child receives color a given that its parent has color b. The associated inference problem is known as the Tree Reconstruction Problem.

A classical result, the Kesten–Stigum bound, characterizes a sharp threshold: above the bound, simply counting the colors at the leaves provides enough information to make a reliable guess of the root color, whereas below it, counting reconstruction is impossible.

In our recent work, we identify the Kesten–Stigum bound as a threshold of computational complexity. Specifically, we show that while it may still be statistically possible to infer the root color below the bound, any algorithm achieving this must overcome a complexity barrier.

I will aim to make this talk accessible to a broad audience, beyond probability.

This is a joint work with Elchanan Mossel.