Speaker: Dana Randall, Georgia Institute of Technology
Abstract: Markov chain Monte Carlo methods have become ubiquitous across science and engineering as a means of exploring large configuration spaces. The idea is to walk among the configurations so that even though you explore a very small part of the space, samples will be drawn from a desirable distribution. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose, largely building on insights from statistical physics. One of the striking discoveries has been the realization that many natural Markov chains undergo a phase transition where they change from begin efficient to inefficient as some parameter of the system is modified. In this talk we will explore this phenomenon, and show how insights from computing reveal interesting results in other fields, including colloids, models of segregation and asynchronous models of programmable matter.