Phase Transitions And Algorithmic Complexity

June 3 - 5, 2002

Schedule

All times in this Schedule are Pacific Time (PT)

Monday, June 3, 2002

Morning Session
8:45 - 9:00 Welcome and Opening Remarks
9:00 - 10:30
10:30 - 11:30 Coffee Break
11:30 - 12:30
Cristopher Moore (University of New Mexico / Santa Fe Institute)

Mick gets what he needs
PDF Presentation
12:30 - 2:00 Lunch (Hosted by IPAM)

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

Statistical Physics in ordered systems (Tutorial)
PDF Presentation
4:00 - 4:30 Coffee Break
4:30 - 5:30
Bela Bollobas (Cambridge University / University of Memphis)

Finite bootstrap percolation
PDF Presentation

Tuesday, June 4, 2002

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

Statistical physics of random combinatorial problems (Tutorial)
PDF Presentation
Presentation (PowerPoint File)
10:30 - 11:00 Coffee Break
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
12:00 - 2:00 Lunch (on your own)

Afternoon Session
2:00 - 3:30
3:30 - 4:00 Coffee Break
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:00 - 5:15 Break
5:15 - 6:15
6:15 Dinner (Hosted by IPAM)

Wednesday, June 5, 2002

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

The principle of deferred decisions
PDF Presentation
9:30 - 10:30
10:30 - 11:00 Coffee Break
11:00 - 12:00
David Wilson (Microsoft Research)

nu >= 2 for random k-SAT
PDF Presentation
12:00 - 2:00 Lunch (on your own)

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

Randomization of complete SAT procedures and heavy-tailed distributions

3:30 - 4:00 Coffee Break
4:00 - 5:00
John Doyle (California Institute of Technology)

Robustness and algorithmic complexity
Presentation (PowerPoint File)