CAM colloquium - April 23 (Joint with IGERT Program in Nonlinear Systems)

Jennifer Tour Chayes
Microsoft Research

"Phase Transitions in Combinatorial Optimization"

Phase transitions are familiar phenomena in physical systems. But they also occur in random versions of combinatorial models, including random versions of some of the canonical problems of theoretical computer science. In this talk, I will illustrate this by discussing joint work with Christian Borgs, Stephan Mertens and Boris Pittel on the so-called random optimum partitioning or load balancing problem -- a fundamental problem in combinatorial optimization. I will show how this problem undergoes a phase transition from a phase in which it is typically possible to balance loads to a phase in which such balance cannot be achieved. I will also discuss how notions of phase transitions may help us to understand what makes hard problems hard, with possible implications for complexity theory and possible applications in cryptograpy. No previous knowledge of phase transition will be assumed in this talk.