• Calendar

January 18, Tuesday
12:00 – 13:30

In the broadcast model on a tree, information is sent from the root over the edges which act like independent noisy channels, to the leaves of the tree at depth n. The reconstruction problems asks whether the information at the root can be recovered from random observations of the leaves with good probability as n becomes larger. This problem arises naturally in biology, information theory and statistical physics. The analysis involves understanding the tradeoff between the replication of information over the leaves and the increasing noise as the distance from the root increases. There is evidence that reconstruction on trees plays an important role in explaining threshold phenomena in random constraint satisfaction problems such as Random k-SAT or random colorings of a random graph as well as the efficiency of finding and sampling solutions for these problems. In this talk, I will present tight bounds on the threshold for reconstruction for independent sets and results on the colorings reconstruction problem on trees. I will also mention algorithmic implications and the connection with random constraint satisfaction problems. Based on joint works with Sly and Tetali; Maneva; and Vera, Vigoda and Weitz.