at the

American Institute of Mathematics, Palo Alto, California

organized by

This workshop, sponsored by AIM and the NSF, will address basic questions about the mixing times of Markov chains. The mixing times of Markov chains are fundamental parameters that encode key geometric information about the chain and at the same time have a wide variety of applications. Markov chain Monte Carlo methods were first used by physicists as a means for simulating Gibbs measures. In the last twenty years, computer scientists and probabilists have brought new perspectives and methods to this study. They have also applied it to other areas, such as approximately uniform sampling and approximate counting of complex combinatorial structures, and to the computation of high-dimensional volumes and integrals.

We intend for the workshop to try and make progress on one of the fundamental open questions about mixing times of Markov chains:

- When is there a
*sharp threshold*for the*total variation*mixing time?

Because these questions have applications in such a wide variety of fields, a rich variety of techniques have been developed to study mixing times, including: probabilistic methods involving martingales, large deviations, and coupling; analytic methods involving spectral gap estimates, log-Sobolev inequalities and hypercontractivity; combinatorial methods involving canonical paths, flows and optimal cutsets; and geometric ideas relating isoperimetric inequalities to eigenvalues of the Laplacian. By bringing together experts on a variety of these different techniques, we hope that perhaps some of them can be combined or modified to obtain the necessary insights into the problems.

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and working sessions.

Invited participants include D. Aldous, L. Babai, G. Ben Arous, F. Chung, R. D'Souza, A. Dembo, P. Diaconis, J. Fill, A. Gamburd, N. Gantert, S. Goel, S. Goldwasser, T. Hayes, A. Karlin, G. Kordzakhia, M. Mihail, B. Morris, E. Mossel, A. Nachmias, Y. Peres, A. Puha, P. Ralph, D. Randall, D. Revelle, L. Saloff Coste, C. Schoolfield, D. Shah, S. Sheffield, A. Sinclair, P. Tetali, V. Vu, E. Wilmer, D. Wilson, P. Winkler, and D. Zhan.

The deadline to apply for support to participate in this workshop has passed.

Plain text announcement or brief announcement.

Go to the
American Institute of Mathematics.

Return to the
AIM Research Conference Center.