DIMACS Workshop Statistical Physics Methods in Discrete Probability, Combinatorics and Theoretical Computer Science
Statistical Physics Methods in Discrete Probability, Combinatorics and Theoretical Computer Science Workshop schedule: Sunday, March 23, 1997 (IAS) 8:00 (sharp) Bus pick-up Breakfast 9:30-9:55 Opening 10:05-10:55 Bela Bollabas Cambridge University and the University of Memphis The phase transition in random graphs. 11:00-11:25 Break 11:25-11:50 Boris Pittel, Ohio State University Sudden emergence of a giant k-core in a randomly evolving graph. (work with Joel Spencer and Nicholas Wormald) 12:00-12:25 Christian Borgs, Institute for Advanced Study and Microsoft Birth of the infinite cluster: A new look at percolation. (work with Jennifer Chayes, Harry Kesten and Joel Spencer) 12:30-2:00 Lunch 2:00-2:50 Scott Kirkpatrick, IBM Satisfiability and phase transitions. 3:00-3:25 Ehud Friedgut, Hebrew University Sharp thresholds for graph properties and the k-sat problem. 3:30-4:00 Tea 4:05-4:30 Bernard Derrida, Ecole Normale Superieur, Paris Non-trivial exponents in the dynamics of the 1d Potts model. 5:00-6:00 Diane Hernek, UCLA Review Session: Computer science 6:15-7:00 Reception 7:00 Dinner Monday, March 24, 1997 (IAS) 8:00 (sharp) Bus pick-up Breakfast 9:30-10:20 Alistair Sinclair, University of California at Berkeley and ICSI Convergence rates for Monte Carlo experiments. 10:30-10:55 Mark Jerrum, University of Edinburgh The Swendsen-Wang process does not always mix rapidly. (work with Vivek Gore) 11:00-11:25 Break 11:25-11:50 Alan Frieze, Carnegie Mellon University Log-Sobolev inequalities and sampling from log-concave distributions. (work with Ravi Kannan) 12:00-12:25 David Aldous, University of California at Berkeley A Metropolis-type optimizatoin algorithm on the infinite tree. 12:30-2:00 Lunch 2:00-2:25 Nati Linial, Hebrew University Covering maps among graphs, random lifts and their applications. 2:35-3:35 Problem Session 3:40-4:15 Tea 4:15-5:15 Problem Session 5:30-6:30 Jacob van den Berg, CWI Review Session: Phase transitions 7:00 Dinner Tuesday, March 25, 1997 (DIMACS) 8:00,8:30 Van pick-up Breakfast 9:00-9:25 David Reimer, Institute for Advanced Study Probabilites on disjoint sets: A proof of the van den Berg-Kesten conjecture. 9:35-10:00 Robert Langlands, Institute for Advanced Study Numerical experiments for the Ising model. 10:05-10:30 Break 10:30-11:20 Michael Aizenman, Princeton University Critical percolation. 11:30-11:55 Gordon Slade, McMaster University Lattice trees, percolation and super-Brownian motion. 12:00-2:00 Lunch 2:00-2:25 Yuval Peres, Hebrew University The Ising model on general trees: an introduction. 2:35-3:00 Robin Pemantle, University of Wisconsin Recursions on trees related to particle systems. (work with Yuval Peres) 3:00-3:40 Tea 3:40-4:30 Leonard Schulman, Georgia Insitute of Technology Computation in the presense of noise. 4:40-5:05 Claire Kenyon, Ecole Normale Superieur, Lyon Error-resilient DNA computing 6:00 Dinner Wednesday, March 26, 1997 (DIMACS) 8:00,8:30 Van pick-up Breakfast 9:00-9:25 Jacob van den Berg, CWI Dependent random graphs and spatial epidemics. 9:35-10:25 Peter Winkler, Lucent Technologies Hard constraints and the Bethe lattice. 10:30-10:55 Break 10:55-11:20 Jeff Stief, University of Gothenburg Phase transitions for Markov random fields: some results and some questiosn. 11:30-11:55 Eric Vigoda, University of California at Berkeley Approximately counting up to four. 12:00-2:00 Lunch 2:00-2:25 James Propp, MIT Coupling-from-the-past for unbiased Monte Carlo sampling. 2:35-3:00 Alan Sokal, NYU Monte Carlo methods for self-avoiding walks. 3:00-3:35 Tea 3:40-4:40 Problem Session 4:50-5:50 Problem Session 6:30 Dinner Thursday, March 27, 1997 (DIMACS) 8:00,8:30 Van pick-up Breakfast 9:00-9:25 Veronique Gayrard, CNRS Gibbs states in the Hopfield model. 9:35-10:00 Chuck Newman, Courant Institute Greedy spin glasses. 10:00-10:30 Break 10:30-10:55 Michel Talagrand, Ohio State University Rigourous results for spin glasses at high and low temperature. 11:05-11:55 Geoffrey Grimmett, Cambridge University Percolation and the random cluster model. 12:00-2:00 Lunch 2:00-2:50 Dominic Welsh, Oxford University Computational Complexity of the Tutte polynomial. 3:00-3:25 Joel Spencer, Courant Institute Why 4/3? A birth model explanation for scaling in the random graph. 3:35-4:00 Jean Bourgain, Institute for Advanced Study Sharp threshold intervals. Tea