Phase transitions are abrupt changes in the global behavior of a system when an external parameter is varied. They are familiar phenomena in physical systems. But such behavior also occurs in many probabilistic 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; and satisfiability -- a canonical model in theoretical computer science which undergoes a 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 the percolation and the satisfiability models 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 cryptography.

No prior knowledge of phase transitions, percolation or satisfiability will be assumed in this talk.

 
Weekly Calendar |  Mathematics Seminars |  Colloquia Schedule |  Conferences |  Calendar Archives