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

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