Colloquium
3:30 p.m., Friday
Math 100
Jennifer Chayes
Microsoft Research
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.
|