Nayantara Bhatnagar - University of Jerusalem

Starts: 4:00 pm on Tuesday, October 12, 2010
Ends: 5:00 pm on Tuesday, October 12, 2010
Location: MCS 149

TITLE: Reconstruction Threshold for the Hardcore Model ABSTRACT: The reconstruction problem on the tree was originally studied as a problem in statistical physics but has since found many applications including in computational phylogenetic reconstruction, the study of the geometry of the space of random constraint satisfaction problems and the mixing time of Markov chains. For a Markov model on an infinite tree the reconstruction problem asks when do the states at level $n$ provide non-trivial information about the state at the root as $n$ goes to infinity. In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the non-reconstruction regime on the $(k+1)$-regular tree. Our bound is almost tight when compared with the known bounds on the reconstruction regime. (Joint work with Allan Sly and Prasad Tetali.)