Random Sampling, Random Structures and Phase Transitions

Sampling algorithms using Markov chains arise in many areas of computation, engineering, and science. The idea is to perform a random walk among the elements in a large state space so that samples chosen from the stationary distribution are useful for the application. In order to get reliable results efficiently, we require the chain to be rapidly mixing, or quickly converging to equilibrium. Often there is a parameter of the system (typically related to temperature or fugacity) so that at low values many natural chains converge rapidly while at high values they converge slowly, requiring exponential time. This dichotomy is often related to phase transitions in the underlying models. In this talk we will explain this phenomenon, giving examples from the natural and social sciences, including magnetization, lattice gasses, colloids, and models of segregation.

发言人详细信息

Dana Randall is the Advance Professor of Computing and an Adjunct Professor of Mathematics at the Georgia Institute of Technology. Her research in randomized algorithms focuses on the design and analysis of efficient algorithms for sampling and approximate counting, using techniques from computing, discrete mathematics and statistical physics. Dr. Randall received her A.B. in Mathematics from Harvard and her Ph.D. in Computer Science from U.C. Berkeley and held postdoctoral positions at the Institute for Advanced Study and Princeton. She is a Fellow of the American Mathematical Society, a National Associate of the National Academies, and the recipient of a Sloan Fellowship and an NSF Career Award.

日期：
演讲者：
Dana Randall
所属机构：
Georgia Institute of Technology