Phase Transitions And Algorithmic Complexity
June 3 - 5, 2002
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:
Dimitris Achlioptas (Microsoft Research)
Christian Borgs (Microsoft Research)
Anton Bovier (Weierstrass Institute, Berlin)
Jennifer Chayes (Microsoft Research)
Rémi Monasson (École Normale Superieure, Paris)
Institute for Pure and Applied Mathematics (IPAM)