Friday, March 21, 2008
11:00 AM
Computer Studies Bldg. Room 209
Dr. Eric Vigoda
Georgia Institute of Technology
Random Colorings: Phase Transitions and Rapid Mixing
A key property (and justification for) models of interest in statistical physics is that they exhibit phase transitions, as occur in nature when a small change in some parameter controlling microscopic interactions of the system causes a dramatic change (in fact a discontinuity) in the macroscopic properties of the system (e.g., the density of water as the temperature passes through the boiling point).

In this talk we'll look at several examples of phase transitions for the case of random colorings. We'll look at algorithms for studying these models, namely algorithms for efficiently generating a random coloring and approximately counting the number of such colorings. The overall theme will be possible connections between phase transitions and the efficiency of related algorithms.

Bio: Dr. Eric Vigoda is an associate professor of Computer Science at Georgia Institute of Technology. He received his PhD in Computer Science from UC Berkeley in 1999. Prior to joining Georgia Tech in 2004, he was a faculty member at the University of Chicago. His research focuses on randomized algorithms. His work with M. Jerrum and A. Sinclair on approximating the permanent was a co-winner of the 2006 Fulkerson prize, which is awarded triennially for outstanding publications in discrete mathematics.

Refreshments will be provided at 10:45