Markov chain Monte Carlo methods

Workshop theme

"Markov-Chain Monte Carlo" (MCMC) is a technique for generating random samples from a specified probability distribution --- often one of a combinatorial or statistical-mechanical nature --- by simulating a Markov chain whose state space includes the structures of interest. MCMC methods are widely applied in diverse areas such as computational biology, astronomy, finance, statistics, computer science and statistical physics. MCMC methods are only applicable when the Markov chain converges rapidly to the target distribution. The mathematical analysis of MCMC methods, focusing on the rate of convergence to equilibrium, has become a highly developed branch of probability theory and theoretical computer science. Lately, ideas from statistical physics and elsewhere have led to a number of variants and alternatives to the MCMC methodology. The study of these alternatives requires the development of new mathematical techniques.

This workshop aims to bring together researchers from all the above-mentioned areas with the goal of deepening cooperation and promoting the cross-fertilization of ideas.

Topics will include (but are not limited to):

The context: models, problems and ideas from physics and elsewhere.
Probabilistic and analytic techniques for MCMC (sophisticated couplings, Martingale methods, log-Sobolev, cutoff).
Developments of MCMC, and competing techniques.
Computational perspectives (including fundamental complexity-theoretic barriers).

Keynote Speakers will include

Eric Vigoda (Georgia Tech), Fabio Martinelli (Rome) and Prasad Tetali (Georgia Tech).

The application is closed

Timetable

Tuesday 25th March 2008
08:30 to 09:55	Registration	Room 1
10:00 to 11:00	Eric Vigoda Random colorings	Room 1
11:10 to 11:40	Coffee	No Room Required
11:40 to 12:30	Can extra updates delay mixing?	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 14:30	Catherine Greenhill University of New South Wales Asymptotic enumeration of contingency tables	Room 1
14:35 to 15:05	Peter Cameron Queen Mary University of London A Markov chain for certain triple systems	Room 1
15:10 to 15:40	Tea	No Room Required
15:40 to 16:10	Glauber dynamics for the Ising Model on the Complete Graph	Room 1
16:15 to 16:45	Ravindran Kannan Microsoft (UK) A new probability inequality and some optimal concentration results	Room 1
16:50 to 17:20	David Levin University of Oregon Ising Model on Kn: mixing time for Glauber dynamics at critical ϐ	Room 1
17:30 to 18:30	Welcome Wine Reception	No Room Required
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	No Room Required

Wednesday 26th March 2008
09:30 to 10:30	Fabio Martinelli Università degli Studi Roma Tre The east model: a case study from glassy dynamics	Room 1
10:35 to 11:05	Allan Sly University of California, Berkeley Rapid mixing of Gibbs sampling on graphs that are sparse on average	Room 1
11:10 to 11:40	Coffee	No Room Required
11:40 to 12:10	James Fill On hitting times and fastest strong stationary times for birth-and-death chains and other skip-free chains	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 14:30	Eyal Lubetzky Microsoft (UK) Cutoff in total variation for birth-and-death chains	Room 1
14:35 to 15:05	Ravi Montenegro University of Massachusetts A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm	Room 1
15:10 to 15:40	Tea	No Room Required
15:40 to 16:10	Magnus Bordewich Durham University Path coupling without contraction	Room 1
16:15 to 16:45	Colouring random graphs randomly	Room 1
16:50 to 17:20	Colin Cooper King's College London Multiple random walks in random regular graphs	Room 1
19:30 to 23:00	Conference Dinner - Corpus Christi College (The Dining Hall)	No Room Required

Thursday 27th March 2008
09:30 to 10:00	Prasad Tetali Georgia Institute of Technology Parking functions and acyclic orientations	Room 1
10:05 to 10:35	Jacob van den Berg Centrum voor Wiskunde en Informatica (CWI) Rapidly mixing Markov chains and the sharp transition in 2D ising percolation	Room 1
10:40 to 11:10	Alan Frieze Carnegie Mellon University Log-concave random graphs	Room 1
11:10 to 11:40	Coffee	No Room Required
11:40 to 12:10	Senya Shlosman Centre de Physique Théorique, Marseille Properties of the interfaces in the multyphase regimes	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 14:30	Dana Randall Georgia Institute of Technology Proving slow mixing with fault lines and fat contours	Room 1
14:35 to 15:05	Alan Sokal An introduction to dynamic critical phenomena and cluster algorithms	Room 1
15:10 to 15:40	Tea	No Room Required
15:40 to 16:10	Jonathan Machta University of Massachusetts Graphical representations and cluster algorithms	Room 1
16:15 to 17:00	Open problem session	Room 1
17:00 to 17:30	Wine and Cheese Reception	No Room Required
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	No Room Required

Friday 28th March 2008
09:30 to 10:00	David Wilson Microsoft (UK) Card shuffling and Diophantine approximation	Room 1
10:05 to 10:35	Near Boltzmann-Gibbs measure preserving stochastic variational integrator	Room 1
10:40 to 11:10	Benedetto Scoppola Università degli Studi di Roma Tor Vergata Randomised algorithms for the maximum clique problem	Room 1
11:10 to 11:40	Coffee	No Room Required
11:40 to 12:10	What happens to a random walk before equilibrium?	Room 1
12:15 to 12:45	Artur Czumaj University of Warwick Testing expansion in bounded degree graphs	Room 1
12:45 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 14:30	Bank sampling: a practical proposal for sampling from isolated maxima with the Metropolis algorithm	Room 1
14:35 to 15:05	Nayantara Bhatnagar University of California, Berkeley Extremality of Gibbs measure for colorings on trees	Room 1
15:05 to 15:35	Tea	No Room Required
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	No Room Required

Speakers

Nayantara Bhatnagar University of California, Berkeley
Magnus Bordewich Durham University
Peter Cameron Queen Mary University of London
Colin Cooper King's College London
Artur Czumaj University of Warwick
James Fill
Alan Frieze Carnegie Mellon University
Catherine Greenhill University of New South Wales
Ravindran Kannan Microsoft (UK)
David Levin University of Oregon
Eyal Lubetzky Microsoft (UK)
Jonathan Machta University of Massachusetts
Fabio Martinelli Università degli Studi Roma Tre
Ravi Montenegro University of Massachusetts
Dana Randall Georgia Institute of Technology
Benedetto Scoppola Università degli Studi di Roma Tor Vergata
Senya Shlosman Centre de Physique Théorique, Marseille
Allan Sly University of California, Berkeley
Alan Sokal
Prasad Tetali Georgia Institute of Technology
Jacob van den Berg Centrum voor Wiskunde en Informatica (CWI)
Eric Vigoda
David Wilson Microsoft (UK)

Show All

Workshop theme

Keynote Speakers will include

The application is closed

Timetable

Speakers

Supported By

Register for updates