Cover times, blanket times, and the Gaussian free field
Interdisciplinary Stochastic Processes Colloquium
Oct 12, 2010, 04:10 PM - 05:00 PM | 60 Evans Hall | Happening As Scheduled
Yuval Peres, Microsoft Research Theory Group
The cover time of a finite graph G (the expected time for simple random walk to
visit all vertices) has been extensively studied, yet a number of fundamental
questions concerning cover times have remained open: Aldous and Fill (1994) asked
whether there is a deterministic polynomial-time algorithm that computes the cover
time up to an O(1) factor; Winkler and Zuckerman (1996) defined the...