4pm Tuesday 28 August 2001
Room 2511, JCMB, King's Buildings
We show how to bound the mixing time and log-Sobolev constants of Markov chains by bounding the edge-isoperimetry of their underlying graphs. To do this we use two recent techniques, one involving Average Conductance and the other log-Sobolev constants. We show a sort of strong conductance bound on a family of geometric Markov chains, give improved bounds for the mixing time of a Markov chain on balanced matroids, and in both cases
(Joint work with Ravi Montenegro.)
Martin Grohe
Wednesday, 22 August 2001
An error occured whilst processing this directive