Probability Seminar: Nayantara Bhatnagar

Abstract:

For spin systems on a tree, roughly, the reconstruction problem is to determine whether correlations persist between vertices deep inside the tree and the root. Reconstruction on trees plays an important role in explaining threshold phenomena in random constraint satisfaction problems on sparse random graphs as well as the efficiency of finding and sampling solutions for these problems.

In this talk, I will speak about the following results:

(1) Bounds on the reconstruction threshold for colorings and rapid mixing of the block dynamics for sampling colorings. (with Vera, Vigoda, and Weitz '11)

(2) An algorithm to compute the reconstruction threshold, with an application showing bounds on the threshold for the Potts model on small-degree trees. (with Maneva '11)