Thursday, May 13

Markov Chain Approaches to Counting and Approximation

(Invited Minisymposium)

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

10:45-11:10 Sampling Lattice Structures on Regions with Free and Periodic Boundary Conditions
Dana Randall, Georgia Institute of Technology
11:15-11:40 Random Walks on Cayley Graphs and Crypto Algorithms
Ramarathnam Venkatesan, Microsoft Research
11:45-12:10 Multishift and Multiscale Coupling for Use in Exact Sampling Algorithms
David B. Wilson, Microsoft Research
12:15-12:40 Title to be announced
Speaker to be announced

AN99 Home


Program Updates

Speaker Index




LMH, 1/19/99, MMD, 2/2/99