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:Isaac Newton Institute Seminar Series
SUMMARY:Cover times of graphs\, majorizing measures\, and
the Gaussian free field - Lee\, J (Washington)
DTSTART;TZID=Europe/London:20110113T100000
DTEND;TZID=Europe/London:20110113T110000
UID:TALK28840AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/28840
DESCRIPTION:The cover time of a finite graph (the expected tim
e for the simple random walk to visit all the vert
ices) has been extensively studied\, yet a number
of fundamental questions have remained open. We p
resent a connection between the cover time\, the d
iscrete Gaussian free field on the underlying grap
h\, and the Fernique-Talagrand theory of majorizin
g measures. At its most basic level\, this involv
es embedding the graph into Euclidean space via th
e effective resistance\, and then studying the ass
ociated Gaussian process (the image points under r
andom projection) using the geometry of the resist
ance metric\, in combination with Talagrands ultra
metric interpretation of majorizing measures.\n\nT
his allows us resolve a number of open questions.
Winkler and Zuckerman (1996) defined the blanket
time (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 (19
94) asked whether there is a deterministic polynom
ial-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\, Lov
asz\, and Vu (2000). We use the aforementioned c
onnection to deduce a positive answer to the quest
ion of Aldous and Fill and to establish the conjec
ture of Winkler and Zuckerman. These results exten
d to arbitrary reversible finite Markov chains\n\n
This is joint work with Jian Ding (U. C. Berkeley)
and Yuval Peres (Microsoft Research).\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR