Cover times, blanket times, and majorizing measures.
Abstract:
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 James Lee (University of Washington) and Yuval Peres
(Microsoft Research).