Dr. Eric Vigoda
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.
Bio:
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.