[Colloquium] Talk by James Lee, University of Washington April 6, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, April 6, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:	James Lee

From:		University of Washington

Web:		http://www.cs.washington.edu/homes/jrl/

Title:  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 of 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 (1996). 

All these results extend to arbitrary reversible Markov chains. 

Joint work with Jian Ding (U.C. Berkeley) and Yuval Peres (Microsoft Research).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100330/b873c843/attachment.htm