Speaker Allan Sly
Affiliation U.C. Berkeley
Date recorded 6 October 2010
The last decade has seen a growing number of connections between statistical physics phase transitions and the theory of computation. Techniques from spin glasses have transformed the understanding of random constraint satisfaction problems while phase transitions play the central role in the efficiency of a wide class of MCMC algorithms. I will survey recent developments in these areas and describe new results on the complexity of counting independent sets.
©2010 Microsoft Corporation. All rights reserved.
By the same speaker
People also watched
Asymptotic Behavior of the Eden Model with Positively Homogeneous Edge Weights (a.k.a. The Polya Aggregate Model)
Critical slowdown for Ising model on the two-dimensional lattice ; Interfacial Phenomena and Skew Diffusion