# Mathematical Sciences Research Institute

Home » Markov Chains in Algorithms and Statistical Physics

# Workshop

Markov Chains in Algorithms and Statistical Physics January 31, 2005 - February 04, 2005
 Registration Deadline: February 04, 2005 about 9 years ago October 31, 2004 over 9 years ago
Parent Program: Probability, Algorithms and Statistical Physics
Organizers Fabio Martinelli, Alistair Sinclair, Eric Vigoda
Speaker(s)

## Show List of Speakers

Description

"Markov chain Monte Carlo" (MCMC) is a technique for sampling at random from a large combinatorial set by simulating a suitable Markov chain on the set. In the past two decades MCMC has emerged as a powerful algorithmic paradigm, with numerous applications in such areas as approximate counting, volume and integration, combinatorial optimization and statistical inference. Independently, it has been studied in mathematical physics because of its connection with the equilibrium and non-equilibrium properties of important models such as the Ising model. Recent years have seen the rapid development of techniques for the analysis of MCMC algorithms, with applications in all the above areas. These techniques draw from a wide range of mathematical disciplines, including combinatorics, discrete probability, functional analysis, geometry and statistical physics, and there has been significant cross-fertilization between them. This workshop aims to bring together practitioners from all these domains with the aim of furthering this interplay of ideas. Schedule for this Workshop =========================== Monday Jan 31st =============== 9:20 WELCOME & OPENING REMARKS 9:30-10:30 Persi Diaconis (Stanford) "Importance Sampling vs Markov chain Monte Carlo" 10:30-11:00 COFFEE 11:00-11:45 Tom Hayes (UC Berkeley) "General lower bounds for mixing of single-site dynamics on graphs" 11:50-12:35 Catherine Greenhill (University of New South Wales) "Sampling regular graphs and a peer-to-peer network" 12:35-2:15 LUNCH 2:15-3:00 Pietro Caputo (Rome III) "Relaxation times in random shuffles and related Markov chains" 3:05-3:50 Ben Morris (Indiana University and Microsoft Research) "The mixing time of the Thorp shuffle" 3:50-4:30 COFFEE 4:30-5:00 Elchanan Mossel (UC Berkeley) "Shuffling by semi-random transpositions" 5:00-5:30 Sharad Goel (Cornell) "Mixing times for top to bottom shuffles" Tuesday Feb 1st =============== 9:30-10:30 Phillip Geissler (UC Berkeley) "Finding transition pathways by Monte Carlo methods" 10:30-11:00 COFFEE 11:00-11:45 Dror Weitz (Institute for Advanced Study, Princeton) "Glauber dynamics on trees: Boundary conditions and mixing time" 11:50-12:35 Fabio Martinelli (Rome III) "Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree" 12:35-2:15 LUNCH 2:15-3:00 Mary Cryan (Edinburgh) "Approximately counting integral flows and cell-bounded contingency tables" 3:05-3:50 Russell Martin (Warwick) "Strong spatial mixing for lattice graphs with fewer colours" 3:50-4:30 COFFEE 4:30-5:30 Xiaoli Meng (Harvard) "Computing normalizing constants: A bridge between Statistical Physics and Statistical Computing" 5:30 RECEPTION Wednesday Feb 2nd ================= 9:30-10:30 HT Yau (Stanford) "Logarithmic Sobolev inequality for some models of random walks" 10:30-11:00 COFFEE 11:00-11:45 Andrea Montanari (Ecole Normale Superieure, Paris) "Equilibration time for Glauber dynamics on random 3-XORSAT instances" 11:50-12:35 Jim Fill (Johns Hopkins) "Perfect simulation of perpetuities using Coupling Into And From The Past" 12:35- LUNCH, followed by free afternoon Thursday Feb 3rd ================ 9:30-10:30 Laszlo Lovasz (Microsoft Research) "Volume computation: a status report" 10:30-11:00 COFFEE 11:00-11:45 Ravi Kannan (Yale) "Random sub-matrices of a given matrix" 11:50-12:35 Ravi Montenegro (Georgia Tech) "Modified conductance and new Cheeger inequalities" 12:35-2:15 LUNCH 2:15-3:00 Christian Borgs (Microsoft Research) "Slow mixing for Swendsen-Wang dynamics on the torus" 3:05-3:50 David Galvin (Institute for Advanced Study, Princeton) "Slow mixing of local dynamics for proper 3-colourings on regular bipartite graphs" 3:50-4:30 COFFEE 4:30-5:00 Marcus Sammer (Georgia Tech) "Bounds on fastest chains using transportation" 5:00-5:30 David Wilson (Microsoft Research) "How many queries does it take to decide if there's a percolating cluster?" Friday Feb 4th ============== 9:30-10:30 Senya Shlosman (CNRS, Marseille) "Markov chains of queueing networks and their infinite volume limits" 10:30-11:00 COFFEE 11:00-11:45 Jason Schweinsberg (UC San Diego) "Family size distributions for multitype Yule processes" 11:50-12:35 Rob van den Berg (CWI and VUA, Amsterdam) "Conditional correlation inequalities for percolation and contact processes" 12:35-2:15 LUNCH 2:15-3:00 Peter Winkler (Dartmouth) "Mixing among the reals" 3:05-3:50 Alan Frieze (Carnegie Mellon) "Random walks on random graphs" 3:50 END OF WORKSHOP

Funding & Logistics

## Show Funding

To apply for funding, you must register by the funding application deadline displayed above.

Students, recent Ph.D.'s, women, and members of underrepresented minorities are particularly encouraged to apply. Funding awards are typically made 6 weeks before the workshop begins. Requests received after the funding deadline are considered only if additional funds become available.

## Show Lodging

MSRI has preferred rates at the Rose Garden Inn, depending on room availability. Reservations may be made by calling 1-800-992-9005 OR directly on their website. Click on Corporate at the bottom of the screen and when prompted enter code MATH (this code is not case sensitive). By using this code a new calendar will appear and will show the MSRI rate on all room types available.

MSRI has preferred rates at the Hotel Durant. Reservations may be made by calling 1-800-238-7268. When making reservations, guests must request the MSRI preferred rate. If you are making your reservations on line, please go to this link and enter the promo/corporate code MSRI123. Our preferred rate is $129 per night for a Deluxe Queen/King, based on availability. MSRI has preferred rates of$149 - $189 plus tax at the Hotel Shattuck Plaza, depending on room availability. Guests can either call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Inst. discount; or go to www.hotelshattuckplaza.com and click Book Now. Once on the reservation page, click “Promo/Corporate Code“ and input the code: msri. MSRI has preferred rates of$110 - \$140 at the Berkeley Lab Guest House, depending on room availability. Reservations may be made by calling 510-495-8000 or directly on their website. Select “I am an individual traveler affiliated with MSRI”.

Additional lodging options may be found on our short term housing page.

## Show Visa/Immigration

Schedule
Jan 31, 2005
Monday
 09:30 AM - 10:30 AM Importance Sampling vs Markov chain Monte Carlo Persi Diaconis (Stanford University) 11:00 AM - 11:45 AM General lower bounds for mixing of single-site dynamics on graphs Thomas Hayes 11:50 AM - 12:35 PM Sampling regular graphs and a peer-to-peer network Catherine Greenhill 02:15 PM - 03:00 PM Relaxation times in random shuffles and related Markov chains Pierto Caputo 03:05 PM - 03:50 PM The mixing time of the Thorp shuffle Ben Morris 04:30 PM - 05:00 PM Shuffling by semi-random transpositions Elchanan Mossel (University of California, Berkeley) 05:00 PM - 05:30 PM Mixing times for top to bottom shuffles Sharad Goel
Feb 01, 2005
Tuesday
 09:30 AM - 10:30 AM Finding transition pathways by Monte Carlo methods Phillip Geissler 11:00 AM - 11:30 AM Glauber dynamics on trees: Boundary conditions and mixing time 11:50 AM - 12:35 PM Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree Fabio Martinelli 02:15 PM - 03:00 PM Approximately counting integral flows and cell-bounded contingency tables Mary Cryan 03:05 PM - 03:50 PM Strong spatial mixing for lattice graphs with fewer colours Russell Martin 04:30 PM - 05:30 PM Computing normalizing constants: A bridge between Statistical Physics and Statistical Computing Xia-Li Meng
Feb 02, 2005
Wednesday
 09:30 AM - 10:30 AM Logarithmic Sobolev inequality for some models of random walks Horng-Tzer Yau 11:00 AM - 11:45 AM Equilibration time for Glauber dynamics on random 3-XORSAT instances Andrea Montanari (Stanford University) 11:50 AM - 12:35 PM Perfect simulation of perpetuities using Coupling Into And From The Past James Fill
Feb 03, 2005
Thursday
 09:30 AM - 10:30 AM Volume computation: a status report László Lovász (Eötvös Loránd University (ELTE)) 11:00 AM - 11:45 AM Random sub-matrices of a given matrix Edward Adelson 11:50 AM - 12:35 PM Modified conductance and new Cheeger inequalities Ravi Montenegro 02:15 PM - 03:00 PM Slow mixing for Swendsen-Wang dynamics on the torus Christian Borgs 03:05 PM - 03:50 PM Slow mixing of local dynamics for proper 3-colourings on regular bipartite graphs David Galvin 04:30 PM - 05:00 PM Bounds on fastest chains using transportation Marcus Sammer 05:00 PM - 05:30 PM How many queries does it take to decide if there's a percolating cluster? David Wilson (University of Washington)
Feb 04, 2005
Friday
 09:30 AM - 10:30 AM Markov chains of queueing networks and their infinite volume limits Senya Shlosman 11:00 AM - 11:45 AM Family size distributions for multitype Yule processes Jason Schweinsberg 11:50 AM - 12:35 PM Conditional correlation inequalities for percolation and contact processes Rob van den Berg 02:15 PM - 03:00 PM Mixing among the reals Peter Winkler (Dartmouth College) 03:05 PM - 03:50 PM Random walks on random graphs Alan Frieze