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 30 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 being efficient to inefficient as some parameter of the system is varied. In this talk we will explore this phenomenon, and show how insights from computing and probability reveal interesting results for asynchronous models of programmable matter.

Speaker Bio: Dana Randall is the ADVANCE Professor of Computing and co-Executive Director of the Institute for Data Engineering and Science (IDEaS) at Georgia Tech. Her research on randomized algorithms focuses on designing efficient sampling algorithms and her work has helped create an interdisciplinary field bridging computer science, discrete probability, and statistical physics. Randall is a Fellow of AMS and a national associate of The National Academies. Randall gave the AMS Arnold Ross Lecture to high school students and their teachers in 2009 and delivered AMS Invited Addresses at the Joint Mathematics Meetings in Baltimore in 2003 and 2018. She chaired the program committee for the Symposium on Discrete Mathematics in 2011 and was co-chair of the SIAM Conference on Discrete Mathematics in 2016. Previously, she was a DIMACS/IAS postdoctoral fellow and co-organizer of the DIMACS Special Focus on Discrete Random Systems.

Slides  Video