Workshop

"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