Collaborative Research FRG: Phase Transitions in Stochastics Dynamics and Algorithms

Stanford University, Stanford CA

Investigators

Abstract

0244323 Dembo Stochastic dynamics for spin systems have been investigated for decades by physicists as a means for simulating Gibbs measures. In the last decade, computer scientists and probabilists have brought new perspectives and methods to this study and showed its applicability to approximately uniform sampling, and approximate counting of combinatorial structures. The key factor controlling the running time of such sampling schemes is the mixing time of the dynamics, which can change dramatically when the underlying stationary measure undergoes a phase transition. A central aim of this FRG project is to explore systematically the connections between information theory, large deviations, and mixing times for Markov chains. Certain fundamental optimization and search problems (e.g., k-satisfiability with random clauses) exhibit a radical change as the ratio between the input size and the number of unknown parameters is tuned. Understanding these thresholds quantitatively is another focus of the project. A system undergoes a "phase transition" when a small change in its input has a profound, qualitative effect on its behavior. Examples of phase transitions have been studied for decades in physics; more recently, this notion has become important in other areas, notably in connection with the performance of search and optimization techniques. Further progress on the hard problems of the subject requires long-term cooperation of researchers in probability and algorithms, as well as consultation with experts in the adjoining areas of combinatorics and statistical physics. The project is expected to have an impact on the design and analysis of randomized algorithms and provide insight on key scheduling and optimization problems. Significant effects on graduate training of students in discrete probability and computer science are expected, as they learn the language and tools of the different disciplines involved.