Program

DIMACS Workshop Statistical Physics Methods in Discrete Probability, Combinatorics and Theoretical Computer Science

Sunday, March 23 - Thursday, March 27, 1997

Sunday, March 23 - Monday, March 24, 1997 at the Institute for Advanced Study, Princeton, NJ;
Tuesday, March 25 - Thursday, March 27, 1997 at DIMACS, CoRE Building, Rutgers University


        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

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on March 20, 1997.