BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:Cover times\, blanket times\, and the Gaussian fre
e field. - Yuval Peres Microsoft Research\, Redmo
nd
DTSTART;TZID=Europe/London:20111101T141500
DTEND;TZID=Europe/London:20111101T151500
UID:TALK33593AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/33593
DESCRIPTION:The cover time of a finite graph G \n(the expected
time for simple random walk to visit all vertices
) has been extensively studied\, yet a\nnumber of
fundamental questions concerning cover times have
remained open:\nAldous and Fill (1994) asked wheth
er there is a deterministic\npolynomial-time algor
ithm that computes the cover time up to a bounded\
nfactor\; Winkler and Zuckerman (1996) defined the
blanket time (when the\nempirical distribution of
the walk is within a factor of 2\, say\, of the\n
stationary distribution) and conjectured that the
blanket time is bounded by\nthe cover time multipl
ied by a universal constant.\n\nWe show that the c
over time of G\, normalized by the number of edges
\, is equivalent (up to a universal constant) to t
he square of the expected maximum of the Gaussian
free field on G. We use this connection and Talagr
and's majorizing measure theory to deduce positive
answers to the questions of Aldous-Fill (1994) an
d Winkler-Zuckerman (1996). No prior familiarity w
ith cover times or the Gaussian free field will be
assumed. \n\nTheir basic properties will be expl
ained in the talk.\n\n(Joint work with Jian Ding a
nd James Lee)\n
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0W
B
CONTACT:HoD Secretary\, DPMMS
END:VEVENT
END:VCALENDAR