BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cover times\, blanket times\, and the Gaussian free field. -  Yuva
 l Peres Microsoft Research\, Redmond
DTSTART:20111101T141500Z
DTEND:20111101T151500Z
UID:TALK33593@talks.cam.ac.uk
CONTACT:HoD Secretary\, DPMMS
DESCRIPTION:The cover time of a finite graph G \n(the expected time for si
 mple random walk to visit all vertices) has been extensively studied\, yet
  a\nnumber of fundamental questions concerning cover times have remained o
 pen:\nAldous and Fill (1994) asked whether there is a deterministic\npolyn
 omial-time algorithm that computes the cover time up to a bounded\nfactor\
 ; Winkler and Zuckerman (1996) defined the blanket time (when the\nempiric
 al distribution of the walk is within a factor of 2\, say\, of the\nstatio
 nary distribution) and conjectured that the blanket time is bounded by\nth
 e cover time multiplied by a universal constant.\n\nWe show that the cover
  time of G\, normalized by the number of edges\, is equivalent (up to a un
 iversal constant) to the square of the expected maximum of the Gaussian fr
 ee field on G. We use this connection and Talagrand's majorizing measure t
 heory to deduce positive answers to the questions of Aldous-Fill (1994) an
 d Winkler-Zuckerman (1996). No prior familiarity with cover times or the G
 aussian free field will be assumed.  \n\nTheir basic properties will be ex
 plained in the talk.\n\n(Joint work with Jian Ding and James Lee)\n
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR