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 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.
Specific topics for this workshop will include: random graphs, local search, satisfiability, Markov chain sampling, average-case complexity, percolation, finite size scaling, disordered and glassy systems, frustration, and replica symmetry.
Dimitris Achlioptas
(Microsoft Research)
Bela Bollobas
(Cambridge University / University of Memphis)
Christian Borgs
(Microsoft Research)
Jennifer Chayes
(Microsoft Research)
Allon Percus, Chair
(Los Alamos National Laboratory)
Bart Selman
(Cornell University)
Copyright. All Rights Reserved.