Phase Transitions And Algorithmic Complexity

June 3 - 5, 2002

Schedule


Monday, June 3, 2002

9:00 - 10:30
11:30 - 12:30
Cristopher Moore (University of New Mexico / Santa Fe Institute)

Mick gets what he needs
PDF Presentation

2:00 - 4:00
Christian Borgs and Jennifer Chayes (Microsoft Research)

Statistical Physics in ordered systems (Tutorial)
PDF Presentation

4:30 - 5:30
Bela Bollobas (Cambridge University / University of Memphis)

Finite bootstrap percolation
PDF Presentation


Tuesday, June 4, 2002

9:00 - 10:30
Rémi Monasson (École Normale Superieure, Paris)

Statistical physics of random combinatorial problems (Tutorial)
PDF Presentation
Presentation (PowerPoint File)

11:00 - 11:30
Stephan Mertens (University of Magdeburg, Germany)

The easiest hard problem: phase transitions in integer partitioning
PDF Presentation

11:30 - 12:00
2:00 - 3:30
4:00 - 5:00
Michel Talagrand (Ohio State University / University of Paris, Jussieu)

Self organization in the low temperature phase of spin glass model

5:15 - 6:15

Wednesday, June 5, 2002

9:00 - 9:30
Lefteris Kirousis (University of Patras, Greece)

The principle of deferred decisions
PDF Presentation

9:30 - 10:30
11:00 - 12:00
David Wilson (Microsoft Research)

nu >= 2 for random k-SAT
PDF Presentation

2:00 - 3:00
3:00 - 3:30
Bart Selman (Cornell University)

Randomization of complete SAT procedures and heavy-tailed distributions

4:00 - 5:00
John Doyle (California Institute of Technology)

Robustness and algorithmic complexity
Presentation (PowerPoint File)