Monday, June 03, 2002
|
Morning Session
|
|
8:45 - 9:00
|
Welcome and Opening Remarks
|
|
9:00 - 10:30
|
Dimitris Achlioptas (Microsoft Research)
"Everything You Always Wanted to Know About Theoretical Computer Science (But Were Afraid to Ask) (Tutorial)"
Presentation (PowerPoint File),
Graphs (PDF File),
Formulas (PDF File)
Notes by Stephan Mertens (PDF File)
|
|
10:30 - 11:30
|
Coffee Break
|
|
11:30 - 12:30
|
Cristopher Moore (University of New Mexico / Santa Fe Institute)
"Mick gets what he needs"
Presentation (PDF File)
|
|
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)"
Presentation (PDF File)
|
|
4:00 - 4:30
|
Coffee Break
|
|
4:30 - 5:30
|
Bela Bollobas (Cambridge University / University of Memphis)
"Finite bootstrap percolation"
Presentation (PDF File)
|
Tuesday, June 04, 2002
|
Morning Session
|
|
9:00 - 10:30
|
Rémi Monasson (École Normale Superieure, Paris)
"Statistical physics of random combinatorial problems (Tutorial)"
Presentation (PDF File)
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"
Presentation (PDF File)
|
|
11:30 - 12:00
|
Weixiong Zhang (Washington University)
"Phase Transitions, Backbones, Measurement Precision, and Phase-Inspired Approximation"
Presentation (PDF File)
|
|
12:00 - 2:00
|
Lunch (on your own)
|
Afternoon Session
|
|
2:00 - 3:30
|
Anton Bovier (Weierstrass Institute, Berlin)
"Rigorous results on disordered system: some efforts tounderstand the replica method (Tutorial)"
Presentation (PDF File)
|
|
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
|
Paul Beame (University of Washington)
"A phase transition in proof complexity and its implications for satisfiability search"
Presentation (PowerPoint File)
|
|
6:15
|
Dinner (Hosted by IPAM)
|
Wednesday, June 05, 2002
|
Morning Session
|
|
9:00 - 9:30
|
Lefteris Kirousis (University of Patras, Greece)
"The principle of deferred decisions"
Presentation (PDF File)
|
|
9:30 - 10:30
|
Jeong Han Kim (Microsoft Research)
"The Poisson cloning model for random graphs with applications to k-coreproblems, random 2-SAT, and random digraphs"
Presentation (PDF File)
Presentation (PowerPoint File)
|
|
10:30 - 11:00
|
Coffee Break
|
|
11:00 - 12:00
|
David Wilson (Microsoft Research)
"nu >= 2 for random k-SAT"
Presentation (PDF File)
|
|
12:00 - 2:00
|
Lunch (on your own)
|
Afternoon Session
|
|
2:00 - 3:00
|
Michael Molloy (University of Toronto)
"Satisfiability thresholds for random models of constraint satisfaction problems"
Presentation (PDF File)
|
|
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)
|