Computer Science/Discrete Mathematics Seminar I

The cover time of a graph is one of the most basic and well-studied properties of the simple random walk, and yet a number of fundamental questions concerning cover times have remained open. We show that there is a deep connection between cover times of graphs and Talagrand's majorizing measure theory. In particular, we prove that the cover time can be characterized, up to universal constants, by the majorizing measure value of a certain metric space on the underlying graph. This resolves a number of open questions. For instance, we use this connection to exhibit a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor, answering a question from Aldous-Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph the blanket and cover times are within an O(1) factor. The best previous bound for both these problems was (log log n)^2 for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (1999). All these results extend to arbitrary reversible Markov chains. Joint work with Jian Ding (U.C. Berkeley) and Yuval Peres (Microsoft Research).