###
Thursday, May 13

##
MS15

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*