text: We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph @math is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on @math , scaled by the number of edges in @math . This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was @math for @math -vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).
  @cite_46: On donne des bornes superieures et inferieures sur la fonction generatrice des moments du temps pris par une chaine de Markov pour visiter au moins n des N sous-ensembles selectionnes de son espace d'etats
summary: A fundamental bound of Matthews @cite_46 shows that @math where we recall that @math is the expected hitting time from @math to @math . Using the straightforward lower bound @math , this fact provides a deterministic @math -approximation to @math in @math -node graphs.