Reconstruction on Trees
Adjunct Assistant Professor Nayantara Bhatnagar (University of California, Berkeley)
GENERAL ColloquiumDATE: 2012-02-29
TIME: 16:00:00 - 17:00:00
LOCATION: John Dedman building in Room G35
CONTACT: JavaScript must be enabled to display this email address.
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 results on the threshold for
reconstruction for colorings and algorithms for finding thresholds
(work that is joint with Vera, Vigoda, and Weitz and with Maneva).
I'll also mention results on the reconstruction threshold for
independent sets (work that is joint with Sly and Tetali).
BIO:
https://sites.google.com/site/nayantarabhatnagar/
