BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cover times of graphs\, majorizing measures\, and the Gaussian fre
 e field - Lee\, J (Washington)
DTSTART:20110113T100000Z
DTEND:20110113T110000Z
UID:TALK28840@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:The cover time of a finite graph (the expected time for the si
 mple random walk to visit all the vertices) has been extensively studied\,
  yet a number of fundamental questions have remained open.  We present a c
 onnection between the cover time\, the discrete Gaussian free field on the
  underlying graph\, and the Fernique-Talagrand theory of majorizing measur
 es.  At its most basic level\, this involves embedding the graph into Eucl
 idean space via the effective resistance\, and then studying the associate
 d Gaussian process (the image points under random projection) using the ge
 ometry of the resistance metric\, in combination with Talagrands ultrametr
 ic interpretation of majorizing measures.\n\nThis allows us resolve a numb
 er of open questions.  Winkler and Zuckerman (1996) defined the blanket ti
 me (when the empirical distribution if within a factor of 2\, say\, of the
  stationary distribution) and conjectured that the blanket time is always 
 within O(1) of the cover time. Aldous and Fill (1994) asked whether there 
 is a deterministic polynomial-time algorithm that computes the cover time 
 up to an O(1) factor. The best approximation factor found so far for both 
 these problems was (log log n)^2 for n-vertex graphs\, due to Kahn\, Kim\,
  Lovasz\, and Vu (2000).   We use the aforementioned connection to deduce 
 a positive answer to the question of Aldous and Fill and to establish the 
 conjecture of Winkler and Zuckerman. These results extend to arbitrary rev
 ersible finite Markov chains\n\nThis is joint work with Jian Ding (U. C. B
 erkeley) and Yuval Peres (Microsoft Research).\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR