Research Horizons Seminar
Tuesday, February 23, 2010 - 12:00
1 hour (actually 50 minutes)
Hosted by: Huy Huynh and Yao Li
Sampling from and approximately counting the size of a large set of combinatorial structures has contributed to a renaissance in research in finite Markov chains in the last two decades. Applications are wide-ranging from sophisticated card shuffles, deciphering simple substitution ciphers (of prison inmates in the California state prison), estimating the volume of a high-dimensional convex body, and to understanding the speed of Gibbs sampling heuristics in statistical physics. More recent applications include rigorous estimates on J.M. Pollard's (1979) classical Rho and Kangaroo algorithms for the discrete logarithm problem in finite cyclic groups. The lecture will be a brief (mostly self-contained) introduction to the Markov Chain Monte Carlo (MCMC) methodology and applications, and will include some open problems.