Computer Science Colloquium
    Tuesday 11/01/2011
Time+Place : Tuesday 11/01/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Nayantara Bhatnagar
Affiliation: Hebrew University
Host       : Johann Makowsky
Title      : Reconstruction in Trees
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
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
Visit our home page-   <>
Mon Dec 20 14:54:39 IST 2010
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>