Phase Transitions in Computer Science

Phase transitions are familiar phenomena in physical systems. But they also occur in many probabilistic and combinatoric models, and even in some problems in theoretical computer science. In this talk, I will discuss phase transitions in several systems, including percolation -- a simple probabilistic model which undergoes a critical transition from a disordered to an ordered phase; 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 different type of transition from solvability to insolvability.

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 critical transition behavior emerge from the behavior of large, finite systems? Our results on percolation, satisfiability and optimum partitioning locate the critical windows of the transitions and establish features within these windows. I will also discuss how the notions of phase transitions and finite-size scaling may be useful in understanding what makes hard problems hard, and hence may have long-term applications in cryptography.

No knowledge of phase transitions or computer science will be assumed in this talk.