Computer Science/Discrete Mathematics Seminar II

Consider the process where a signal propagates downward an infinite rooted tree. On every edge some independent noise is applied to the signal. The reconstruction problem asks whether it is possible to reconstruct the original signal given observations of signals received at vertices deep in the tree. This problem was first studied in the 1970s in statistical physics, and has found applications in noisy computation, community detection, genetics, and so on. The hypertree version of the reconstruction problem has relationships with problems such as random constraint satisfaction problems and hypergraph community detection.

In this talk I will discuss some recent progress on reconstruction problems on trees and hypertrees. In particular, for a class of reconstruction on hypertrees problems, we determine the exact reconstruction threshold for a wide range of parameters. Two different methods are used, each with its advantages and drawbacks. One method is based on strong data processing inequalities (SDPIs) and their multi-terminal variants, yielding non-asymptotic impossibility results that are strong and sometimes tight. The other method is based on large degree asymptotics and robust reconstruction, which gives tight impossibility results in the large degree regime. An information theoretic perspective plays an important role in these methods.

Based on joint works with Aaradhya Pandey and Yury Polyanskiy.