Phase Transitions in Computer Science

Phase transitions are familiar phenomena in physical systems. But they also occur in many probabilistic and combinatorial models, including random versions of some classic problems in theoretical computer science. In this talk, I will discuss phase transitions in several systems, including the random graph — a simple probabilistic model which undergoes a critical transition from a disordered to an ordered phase; k-satisfiability — a canonical model in theoretical computer science which undergoes a transition from solvability to insolvability; and optimum partitioning -a fundamental problem in combinatorial optimization, which undergoes a transition from existence to non-existence of a perfect optimizer. Technically, phase transitions only occur in infinite systems. However, real systems and the systems we simulate are large, but finite. Hence the question of finite-size scaling: Namely, how does the transition behavior emerge from the behavior of large, finite systems? Results on the random graph, satisfiability and optimum partitioning locate the critical windows of these transitions and establish interesting features within these windows. No knowledge of phase transitions will be assumed in this talk.

Authors and Affiliations

1. Microsoft Research, One Microsoft Way, 98052, Redmond, WA, USA

   Jennifer Chayes

Editors and Affiliations

1. Compaq Cambridge Research Laboratory, One Cambridge Center, 02142-1612, Cambridge, MA, USA

   Sergio Rajsbaum

Reprints and permissions

© 2002 Springer-Verlag Berlin Heidelberg

Policies and ethics