Phase Transitions And Algorithmic Complexity

June 3 - 5, 2002

Schedule and Presentations

Pictures

Organizing Committee:

Dimitris Achlioptas (Microsoft Research)
Bela Bollobas (Cambridge University / University of Memphis)
Christian Borgs (Microsoft Research)
Jennifer Chayes (Microsoft Research)
Allon Percus (Los Alamos National Laboratory)
Bart Selman (Cornell University)

Introduction

The study of phase transitions in combinatorial problems has a distinguished history, originating with the work of Erdös and Rényi on random graphs almost half a century ago. During the past ten years, there has been a rapidly increasing awareness of the relevance of phase transitions to average-case algorithmic performance on computationally hard problems. It has become clear that theoretical tools developed in the mathematical and physical sciences, involving critical phenomena, are essential to understanding processes fundamental to computation. This goal has lately mobilized mathematicians, physicists and computer scientists alike, leading to a flurry of activity encompassing conjectures, theoretical insights, and numerical as well as rigorous results.

It is now recognized that for a wide range of computational problems defined over ensembles of random instances, the most challenging instances are found near a threshold in parameter space where certain characteristics of the problem change dramatically. In statistical mechanics terms, this may be understood as a phase transition, where the system undergoes a sudden change in microscopic order. Theoretical arguments from the Satisfiability problem - which in certain cases exhibits a replica symmetry breaking (RSB) phase transition similar to that seen in spin glasses - indicate a connection between the nature of the transition and the problem's average-case algorithmic complexity. However, the details of this connection remain tentative. A better understanding of critical phenomena in the context of random combinatorial structures will be a key ingredient to improving our current notions of algorithmic complexity and performance.

On June 3 – 5, 2002, we will hold a 3-day "Hot Topic" workshop at IPAM. Using the tools of discrete mathematics, our goal is to chart the course towards a theory of critical phenomena in algorithmic complexity. To this end, the workshop will bring together researchers from the fields of mathematics, computer science and physics. Specific topics will span all three fields, and may include:

• Random graphs
• Local search
• Satisfiability
• Markov chain sampling
• Average-case complexity
• Percolation
• Finite size scaling
• Disordered and glassy systems
• Frustration
• Replica symmetry

Speakers

Technical speakers
   Paul Beame (University of Washington)
   Bela Bollobas (Cambridge University / University of Memphis)
   John Doyle (California Institute of Technology)
   Jeong Han Kim (Microsoft Research)
   Lefteris Kirousis (University of Patras, Greece)
   Stephan Mertens (University of Magdeburg, Germany)
   Michael Molloy (University of Toronto)
   Cristopher Moore (University of New Mexico / Santa Fe Institute)
   Bart Selman (Cornell University)
   Michel Talagrand (Ohio State University / University of Paris, Jussieu)
   David Wilson (Microsoft Research)
   Weixiong Zhang (Washington University)

Sponsors

Institute for Pure and Applied Mathematics
Intelligent Information Systems Institute
Los Alamos National Laboratory
Microsoft Research

Contact Us:

Institute for Pure and Applied Mathematics (IPAM)
Attn: PTAC2002
460 Portola Plaza
Los Angeles CA 90095-7121
Phone: 310 825-4755
Fax: 310 825-4756
Email: ipam@ucla.edu
Website: http://www.ipam.ucla.edu/programs/ptac2002/