News Archives

[Colloquium] Phase Transitions in Computer Science, Statistics, and Physics

October 24, 2008

Watch Colloquium: 

Quicktime file (348 Megs)
AVI file (560 Megs)


  • Date: Friday, October 24th, 2008 
  • Time: 2 pm — 3:15 pm 
  • Place: ME 218

Thomas Hayes 
Computer Science Department UNM

“Phase transition” refers to a phenomenon, observed in many large-scale physical systems, wherein, as one parameter is slowly changed, a sudden sharp change in the qualitative behavior of the system is observed. For instance, as temperature increases past 100C, a dramatic change takes place in a pot of water. Similarly, an iron bar placed in a magnetic field will tend to suddenly magnetize (with most of the electron spins in the same direction) once the field strength passes a certain threshold.

Similar changes can be observed in a number of systems of interest to computer scientists and statisticians. For instance, one can consider the behavior of the number of satisfying solutions to a Boolean formula, as the number of clauses slowly increases (say, by adding clauses at random). Or one could consider the number of components in a random graph, as a function of the number of edges. Other, closely related topics include: (1) efficient sampling of random configurations of a system using MCMC algorithms, (2) decay of correlations as a function of distance, and (3) uniqueness of something called “Gibbs measure”

I will talk about some old and new results in this area.

Bio: Prof. Tom Hayes received his Ph.D. in Computer Science at the University of Chicago. His thesis was on “Rapidly Mixing Markov Chains for Graph Colorings.” Prior to joining UNM this fall, he did postdoctoral work at U.C. Berkeley and the Toyota Technological Institute at Chicago. His research interests include algorithms, probability, and machine learning.