- Series
- Research Horizons Seminar
- Time
- Tuesday, February 23, 2010 - 12:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Prasad Tetali – Professor, School of Mathematics and School of Computer Science
- Organizer
- Huy Huynh
Please Note: 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.