Monday, October 15, 2007
11:00 AM
CSB 209
Dr. Eric Vigoda
Georgia Institute of Technology
Markov Chain Monte Carlo Methods
We will begin with an introduction to the Markov chain Monte Carlo (MCMC) approach for randomly sampling and approximately counting from large sets. This will include some examples of MCMC applications in a variety of scientific fields. We will then delve into a polynomial time algorithm for approximating the so-called permanent of a matrix, thereby resolving a long-standing open problem. The algorithm uses a sophisticated MCMC approach involving a sequence of Markov chains, where the random samples from one chain are used to design the successive chain.


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.