Seminar by Nayantara Bhatnagar
Reconstruction for Colorings on Trees
Nayantara Bhatnagar
Dept. of Statistics, UC Berkeley
Date: Tuesday, August 25, 2009
Time: 2:00 PM
Venue: CS101.Abstract:
I will talk about two recent results in this talk. Consider the following random assignment of colors to the vertices of a tree of height h where each vertex has D children. First the root is colored with one of k colors uniformly at random. Each vertex thereafter independently chooses one of k-1 colors randomly, different from its parent. Conditioned on having started with two different colors at the root, if the variation distance between the distributions of colorings at the leaves of the tree goes to 0 as the height goes to infinity, reconstruction does not hold. Thresholds for reconstruction have been studied for many models in contexts including statistical physics, information theory and evolutionary biology. For k > D it is easy to show that reconstruction does not hold while for k D/ ln(D), reconstruction is possible. We show that for k > D/ ln(D), reconstruction does not hold. This is joint work with Vera, Vigoda and Weitz.
The distribution of the measure over colors at the root given a typical boundary can be computed using a distributional recurrence. However, the exact computation is infeasible since the support grows exponentially with the depth. In joint work with Maneva, we introduce the notion of a survey of a distribution which is a succinct representation of the true distribution and give an efficient algorithm to compute it. As an application we show bounds on the reconstruction threshold for the Potts model, a generalization of the colorings model, on small-degree trees. The same approach can be applied to a large class of Markov random field models.
About The Speaker:
Dr. Nayantara bhatnagar finished her Ph.D. in "Algorithms, Combinatorics and Optimization" from Georgia Tech. in 2007 under the supervision of Dana Randall and Eric Vigoda. Dr. Bhatnagar's research interests are in theoretical computer science, randomized algorithms, the Markov Chain Monte Carlo method, statistical physics and combinatorial problems in evolutionary biology.