Logo

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 over 9 years ago
To apply for Funding you must register by: October 31, 2004 almost 10 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 All Collapse

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 Directions to Venue

Show Visa/Immigration

Schedule
Show All Collapse
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