EVENT DETAILS AND ABSTRACT

Title: Algorithms for Finding a Random Needle in a Combinatorial Haystack
Speaker: Professor Dana Randall
Speaker Info: Computer Science Department, Georgia Tech
Brief Description:
Special Note:
Abstract:

Markov chain Monte Carlo techniques are used extensively to study properties of large combinatorial sets. From a rigorous standpoint, the two main challenges are developing techniques to analyze the mixing time, or convergence rates, of Markov chains on large state spaces and designing fast Monte Carlo algorithms to address specific applications. In this talk, we will outline some of the techniques used to bound mixing times, focusing on applications arising in statistical physics, combinatorics and computer science. Special attention will be given to how physical concepts such as phase transitions can aid our design and analysis. We will present an overview of some results demonstrating fast mixing and new results demonstrating slow mixing of well-studied chains.