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...