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