Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Abstract: Running a Markov chain is a popular tool used for sampling from various distribution, approximate counting, volume approximation algorithms, etc. However, from a theoretical point of view, these algorithms are good as long as we can estimate mixing time of the Markov chains. In the talk, I will present two general approaches to study the mixing of Markov chains: one based on multicommodity flows, and the other based on the stopping time technique. We then elaborate on their advantages and disadvantages, and apply them to the optimal lifting problem, which can be stated as follows. Suppose one has a finite Markov chain, and one wants to speed up mixing of this Markov chain by lifting it to a bigger space. Turns out, this is often possible indeed, at least in theory. We present a construction of an optimal lifting (up to a constant) This is joint work with F. Chen and L. Lovasz.