Speaker Allan Sly
Host Jennifer Chayes
Date recorded 8 February 2011
The reconstruction problem on the tree concerns the propagation of information in Markov processes on trees and has been studied in probability, statistical physics, computational biology, information theory and theoretical computer science. I will discuss progress in establishing thresholds for the reconstruction problem and give an overview of its applications to phylogenetic reconstruction, mixing times of Markov chains, random constraint satisfaction problems and the computational complexity of counting problems.
©2011 Microsoft Corporation. All rights reserved.
By the same speaker
People also watched
Long-Range Planning with Time-Inconsistency: A Class of Computational Problems in Behavioral Economics