Phase Transitions And Algorithmic Complexity - IPAM

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

08:45-09:00
Welcome and Opening Remarks
09:00-10:30
Dimitris Achlioptas (UC Santa Cruz)
Everything You Always Wanted to Know About Theoretical Computer Science (But Were Afraid to Ask) (Tutorial)
10:30-11:30
Coffee Break
11:30-12:30
Cristopher Moore (Santa Fe Institute)
Mick gets what he needs

Afternoon Session

12:30-14:00
Lunch (Hosted by IPAM)
14:00-16:00
Christian Borgs (Microsoft Research)
Statistical Physics in ordered systems (Tutorial)
16:00-16:30
Coffee Break
16:30-17:30
Bela Bollobas (University of Memphis)
Finite bootstrap percolation

Tuesday, June 4, 2002

Morning Session

09:00-10:30
Rémi Monasson (Centre National de la Recherche Scientifique (CNRS))
Statistical physics of random combinatorial problems (Tutorial)
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
11:30-12:00
Weixiong Zhang (Washington University)
Phase Transitions, Backbones, Measurement Precision, and Phase-Inspired Approximation

Afternoon Session

12:00-14:00
Lunch (on your own)
14:00-15:30
Anton Bovier (Weierstrass Institute, Berlin)
Rigorous results on disordered system: some efforts tounderstand the replica method (Tutorial)
15:30-16:00
Coffee Break
16:00-17:00
Michel Talagrand (Ohio State University / University of Paris, Jussieu)
Self organization in the low temperature phase of spin glass model
17:00-17:15
Break
17:15-18:15
Paul Beame (University of Washington)
A phase transition in proof complexity and its implications for satisfiability search
18:15
Dinner (Hosted by IPAM)

Wednesday, June 5, 2002

Morning Session

09:00-09:30
Lefteris Kirousis (University of Patras, Greece)
The principle of deferred decisions
09:30-10:30
Jeong Han Kim (Yonsei University)
The Poisson cloning model for random graphs with applications to k-coreproblems, random 2-SAT, and random digraphs
10:30-11:00
Coffee Break
11:00-12:00
David Wilson (Microsoft Research)
nu >= 2 for random k-SAT

Afternoon Session

12:00-14:00
Lunch (on your own)
14:00-15:00
Michael Molloy (University of Toronto)
Satisfiability thresholds for random models of constraint satisfaction problems
15:00-15:30
Bart Selman (Cornell University)
Randomization of complete SAT procedures and heavy-tailed distributions
15:30-16:00
Coffee Break
16:00-17:00
John Doyle (California Institute of Technology)
Robustness and algorithmic complexity
Printable Version