McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE: Wednesday, May 17th
TIME: 3:30 PM - 4:30 PM
TITLE: Phase Transitions of Random Graph and Random Satisfiability Problem
SPEAKER: Dr. Jeong Kim, Microsoft Research

There has recently been interest in a new field emerging at the intersection of statistical physics, discrete mathematics, and theoretical computer sciences. The field is characterized by the study of phase transitions in combinatorial structures arising in problems from theoretical computer sciences. The convergence of these three disciplines is a consequence of the recent observation that one can define control parameters in terms of which certain theoretical computer science problems undergo phase transitions, and the even more interesting observation that the hardest instances of these problems seem to be concentrated at the phase transition point. The problem for which this phenomenon has been studied most extensively is the satisfiability problem. We will survey these phenomena of random graph and random satisfiability problem, and how they are related.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at