ABSTRACT

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. No prior knowledge of phase transitions or of particular models will be assumed in this talk. Refreshments will be served in the Lounge (Room 224) at 3:00 p.m. Other Recent and Upcoming Colloquia