Abstract:

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.

Short Bio: 
Nayantara Bhatnagar is currently a postdoctoral researcher in the
School of Computer Science and Engineering at Hebrew University.
Prior to this she was a postdoc in the Statistics Department at
UC Berkeley after completing her PhD in Algorithms, Combinatorics and 
Optimization at Georgia Tech.

=================================
Refreshments served from 14:15 on,
 	Lecture starts at 14:30
=================================