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
cgm-help@cgm.cs.mcgill.ca.