10:45 AM-12:45 PM
Room: Savannah 1
During the past decade, analysis of finite Markov chains has played a key role in the development of randomized algorithms for computational problems. The speakers in this minisymposium will illustrate applications to problems from combinatorics, statistical physics, cryptography, and exact sampling. A standard premise is that the state space of the Markov chain is exponentially large in some input parameter, and a desirable feature of a Markov-chain-based algorithm is that the convergence of the distribution of the chain to its invariant distribution be "rapid" -- polynomial in the same input parameter. Another desirable feature is that the algorithm be stoppable with the guarantee that the underlying Markov chain has exactly attained its invariant distribution.
Organizer: Prasad V. Tetali
Georgia Institute of Technology
LMH, 1/19/99, MMD, 2/2/99