Cover times, blanket times, and majorizing measures

Abstract

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 $G$ is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on $G$, scaled by the number of edges in $G$. 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 $O((\log \log n)^2)$ for $n$-vertex graphs, due to Kahn, Kim, Lovász, and Vu (2000).

  • [Aldous89] D. J. Aldous, Probability Approximations via the Poisson Clumping Heuristic, New York: Springer-Verlag, 1989, vol. 77.
    @book {Aldous89, MRKEY = {0969362},
      AUTHOR = {Aldous, David J.},
      TITLE = {Probability Approximations via the {P}oisson Clumping Heuristic},
      SERIES = {Appl. Math. Sci.},
      VOLUME = {77},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1989},
      PAGES = {xvi+269},
      ISBN = {0-387-96899-7},
      MRCLASS = {60-02 (60C05 60D05 60F05 60J20 60K99)},
      MRNUMBER = {0969362},
      MRREVIEWER = {Georg Lindgren},
      ZBLNUMBER = {0679.60013},
      }
  • [AF] Go to document D. J. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs.
    @misc{AF,
      author={Aldous, David J. and Fill, J.},
      TITLE={Reversible {M}arkov Chains and Random Walks on Graphs},
      NOTE={in preparation},
      URL={http://www.stat.berkeley.edu/~aldous/RWG/book.html},
     }
  • [Aldous82] Go to document D. J. Aldous, "Markov chains with almost exponential hitting times," Stochastic Process. Appl., vol. 13, iss. 3, pp. 305-310, 1982.
    @article {Aldous82, MRKEY = {0671039},
      AUTHOR = {Aldous, David J.},
      TITLE = {Markov chains with almost exponential hitting times},
      JOURNAL = {Stochastic Process. Appl.},
      FJOURNAL = {Stochastic Processes and their Applications},
      VOLUME = {13},
      YEAR = {1982},
      NUMBER = {3},
      PAGES = {305--310},
      ISSN = {0304-4149},
      CODEN = {STOPB},
      MRCLASS = {60J27},
      MRNUMBER = {0671039},
      MRREVIEWER = {Xiang Qun Yang},
      DOI = {10.1016/0304-4149(82)90016-3},
      ZBLNUMBER = {0491.60077},
      }
  • [Aldous91] Go to document D. J. Aldous, "Random walk covering of some special trees," J. Math. Anal. Appl., vol. 157, iss. 1, pp. 271-283, 1991.
    @article {Aldous91, MRKEY = {1109456},
      AUTHOR = {Aldous, David J.},
      TITLE = {Random walk covering of some special trees},
      JOURNAL = {J. Math. Anal. Appl.},
      FJOURNAL = {Journal of Mathematical Analysis and Applications},
      VOLUME = {157},
      YEAR = {1991},
      NUMBER = {1},
      PAGES = {271--283},
      ISSN = {0022-247X},
      CODEN = {JMANAK},
      MRCLASS = {60J15 (05C05 60C05)},
      MRNUMBER = {1109456},
      MRREVIEWER = {Robin Pemantle},
      DOI = {10.1016/0022-247X(91)90149-T},
      ZBLNUMBER = {0733.60092},
      }
  • [Aldous91b] Go to document D. J. Aldous, "Threshold limits for cover times," J. Theoret. Probab., vol. 4, iss. 1, pp. 197-211, 1991.
    @article {Aldous91b, MRKEY = {1088401},
      AUTHOR = {Aldous, David J.},
      TITLE = {Threshold limits for cover times},
      JOURNAL = {J. Theoret. Probab.},
      FJOURNAL = {Journal of Theoretical Probability},
      VOLUME = {4},
      YEAR = {1991},
      NUMBER = {1},
      PAGES = {197--211},
      ISSN = {0894-9840},
      CODEN = {JTPREO},
      MRCLASS = {60J10 (60D05)},
      MRNUMBER = {1088401},
      MRREVIEWER = {Robin Pemantle},
      DOI = {10.1007/BF01047002},
      ZBLNUMBER = {0717.60082},
      }
  • [AKLLR79] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff, "Random walks, universal traversal sequences, and the complexity of maze problems," in 20th Annual Symposium on Foundations of Computer Science, New York: IEEE, 1979, pp. 218-223.
    @incollection {AKLLR79, MRKEY = {0598110},
      AUTHOR = {Aleliunas, Romas and Karp, Richard M. and Lipton, Richard J. and Lov{á}sz, L{á}szl{ó} and Rackoff, Charles},
      TITLE = {Random walks, universal traversal sequences, and the complexity of maze problems},
      BOOKTITLE = {20th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience},
      VENUE={{S}an {J}uan, {P}uerto {R}ico, 1979},
      PAGES = {218--223},
      PUBLISHER = {IEEE},
      ADDRESS = {New York},
      YEAR = {1979},
      MRCLASS = {68E10 (68C25 90C35)},
      MRNUMBER = {0598110},
      }
  • [BDNP09] Go to document M. T. Barlow, J. Ding, A. Nachmias, and Y. Peres, "The evolution of the cover time," Combin. Probab. Comput., vol. 20, iss. 3, pp. 331-345, 2011.
    @article {BDNP09, MRKEY = {2784631},
      AUTHOR = {Barlow, Martin T. and Ding, Jian and Nachmias, Asaf and Peres, Yuval},
      TITLE = {The evolution of the cover time},
      JOURNAL = {Combin. Probab. Comput.},
      FJOURNAL = {Combinatorics, Probability and Computing},
      VOLUME = {20},
      YEAR = {2011},
      NUMBER = {3},
      PAGES = {331--345},
      ISSN = {0963-5483},
      MRCLASS = {05C80 (05C85)},
      MRNUMBER = {2784631},
      DOI = {10.1017/S0963548310000489},
      ZBLNUMBER = {1226.05230},
      }
  • [Biggins77] J. D. Biggins, "Chernoff’s theorem in the branching random walk," J. Appl. Probability, vol. 14, iss. 3, pp. 630-636, 1977.
    @article {Biggins77, MRKEY = {0464415},
      AUTHOR = {Biggins, J. D.},
      TITLE = {Chernoff's theorem in the branching random walk},
      JOURNAL = {J. Appl. Probability},
      FJOURNAL = {Journal of Applied Probability},
      VOLUME = {14},
      YEAR = {1977},
      NUMBER = {3},
      PAGES = {630--636},
      ISSN = {0021-9002},
      MRCLASS = {60J80},
      MRNUMBER = {0464415},
      MRREVIEWER = {Soren Asmussen},
      ZBLNUMBER = {0373.60090},
      }
  • [BK89] Go to document A. Z. Broder and A. R. Karlin, "Bounds on the cover time," J. Theoret. Probab., vol. 2, iss. 1, pp. 101-120, 1989.
    @article {BK89, MRKEY = {0981768},
      AUTHOR = {Broder, Andrei Z. and Karlin, Anna R.},
      TITLE = {Bounds on the cover time},
      JOURNAL = {J. Theoret. Probab.},
      FJOURNAL = {Journal of Theoretical Probability},
      VOLUME = {2},
      YEAR = {1989},
      NUMBER = {1},
      PAGES = {101--120},
      ISSN = {0894-9840},
      CODEN = {JTPREO},
      MRCLASS = {60J10 (05C99)},
      MRNUMBER = {0981768},
      MRREVIEWER = {David J. Aldous},
      DOI = {10.1007/BF01048273},
      ZBLNUMBER = {0681.60063},
      }
  • [Campbell] G. A. Campbell, "Cisoidal oscillations," Trans. Amer. Inst. Elec. Engrs., vol. 30, 1911.
    @article{Campbell,
      author={Campbell, G. A.},
      TITLE={Cisoidal oscillations},
      JOURNAL={Trans. Amer. Inst. Elec. Engrs.},
      VOLUME={30},
      YEAR={1911},
     }
  • [CRRST96] Go to document A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari, "The electrical resistance of a graph captures its commute and cover times," Comput. Complexity, vol. 6, iss. 4, pp. 312-340, 1996/97.
    @article {CRRST96, MRKEY = {1613611},
      AUTHOR = {Chandra, Ashok K. and Raghavan, Prabhakar and Ruzzo, Walter L. and Smolensky, Roman and Tiwari, Prasoon},
      TITLE = {The electrical resistance of a graph captures its commute and cover times},
      JOURNAL = {Comput. Complexity},
      FJOURNAL = {Computational Complexity},
      VOLUME = {6},
      YEAR = {1996/97},
      NUMBER = {4},
      PAGES = {312--340},
      ISSN = {1016-3328},
      CODEN = {CPTCEU},
      MRCLASS = {60J15 (05C90 94C05)},
      MRNUMBER = {1613611},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1007/BF01270385},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {0905.60049},
      }
  • [CF08] Go to document C. Cooper and A. Frieze, "The cover time of the giant component of a random graph," Random Structures Algorithms, vol. 32, iss. 4, pp. 401-439, 2008.
    @article {CF08, MRKEY = {2422388},
      AUTHOR = {Cooper, Colin and Frieze, Alan},
      TITLE = {The cover time of the giant component of a random graph},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {32},
      YEAR = {2008},
      NUMBER = {4},
      PAGES = {401--439},
      ISSN = {1042-9832},
      MRCLASS = {05C80 (60C05)},
      MRNUMBER = {2422388},
      MRREVIEWER = {Jennie C. Hansen},
      DOI = {10.1002/rsa.20201},
      ZBLNUMBER = {1157.05045},
      }
  • [CW90] Go to document D. Coppersmith and S. Winograd, "Matrix multiplication via arithmetic progressions," J. Symbolic Comput., vol. 9, iss. 3, pp. 251-280, 1990.
    @article {CW90, MRKEY = {1056627},
      AUTHOR = {Coppersmith, Don and Winograd, Shmuel},
      TITLE = {Matrix multiplication via arithmetic progressions},
      JOURNAL = {J. Symbolic Comput.},
      FJOURNAL = {Journal of Symbolic Computation},
      VOLUME = {9},
      YEAR = {1990},
      NUMBER = {3},
      PAGES = {251--280},
      ISSN = {0747-7171},
      MRCLASS = {68Q25 (11Y16 15A30)},
      MRNUMBER = {1056627},
      MRREVIEWER = {Werner Hartmann},
      DOI = {10.1016/S0747-7171(08)80013-2},
      ZBLNUMBER = {0702.65046},
      }
  • [DPRZ04] Go to document A. Dembo, Y. Peres, J. Rosen, and O. Zeitouni, "Cover times for Brownian motion and random walks in two dimensions," Ann. of Math., vol. 160, iss. 2, pp. 433-464, 2004.
    @article {DPRZ04, MRKEY = {2123929},
      AUTHOR = {Dembo, Amir and Peres, Yuval and Rosen, Jay and Zeitouni, Ofer},
      TITLE = {Cover times for {B}rownian motion and random walks in two dimensions},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {160},
      YEAR = {2004},
      NUMBER = {2},
      PAGES = {433--464},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {60J65 (60G50)},
      MRNUMBER = {2123929},
      MRREVIEWER = {M. G. Shur},
      DOI = {10.4007/annals.2004.160.433},
      ZBLNUMBER = {1068.60018},
      }
  • [DS84] P. G. Doyle and L. J. Snell, Random Walks and Electric Networks, Washington, DC: Mathematical Association of America, 1984, vol. 22.
    @book {DS84, MRKEY = {0920811},
      AUTHOR = {Doyle, Peter G. and Snell, J. Laurie},
      TITLE = {Random Walks and Electric Networks},
      SERIES = {Carus Math. Monogr.},
      VOLUME = {22},
      PUBLISHER = {Mathematical Association of America},
      ADDRESS = {Washington, DC},
      YEAR = {1984},
      PAGES = {xiv+159},
      ISBN = {0-88385-024-9},
      MRCLASS = {94C05 (60J15 94C15)},
      MRNUMBER = {0920811},
      MRREVIEWER = {H. Kesten},
      ZBLNUMBER = {0583.60065},
      }
  • [Dudley67] Go to document R. M. Dudley, "The sizes of compact subsets of Hilbert space and continuity of Gaussian processes," J. Functional Analysis, vol. 1, pp. 290-330, 1967.
    @article {Dudley67, MRKEY = {0220340},
      AUTHOR = {Dudley, R. M.},
      TITLE = {The sizes of compact subsets of {H}ilbert space and continuity of {G}aussian processes},
      JOURNAL = {J. Functional Analysis},
      VOLUME = {1},
      YEAR = {1967},
      PAGES = {290--330},
      MRCLASS = {60.40 (46.00)},
      MRNUMBER = {0220340},
      MRREVIEWER = {H. Heyer},
      ZBLNUMBER = {0188.20502},
      DOI = {10.1016/0022-1236(67)90017-1},
     }
  • [Dynkin84] Go to document E. B. Dynkin, "Gaussian and non-Gaussian random fields associated with Markov processes," J. Funct. Anal., vol. 55, iss. 3, pp. 344-376, 1984.
    @article {Dynkin84, MRKEY = {0734803},
      AUTHOR = {Dynkin, E. B.},
      TITLE = {Gaussian and non-{G}aussian random fields associated with {M}arkov processes},
      JOURNAL = {J. Funct. Anal.},
      FJOURNAL = {Journal of Functional Analysis},
      VOLUME = {55},
      YEAR = {1984},
      NUMBER = {3},
      PAGES = {344--376},
      ISSN = {0022-1236},
      CODEN = {JFUAAW},
      MRCLASS = {60G20 (60G60 81E08)},
      MRNUMBER = {0734803},
      MRREVIEWER = {Gerhard C. Hegerfeldt},
      DOI = {10.1016/0022-1236(84)90004-1},
      ZBLNUMBER = {0533.60061},
      }
  • [Dynkin83] E. B. Dynkin, "Local times and quantum fields," in Seminar on Stochastic Processes, 1983, Boston, MA: Birkhäuser, 1984, vol. 7, pp. 69-83.
    @incollection {Dynkin83, MRKEY = {0902412},
      AUTHOR = {Dynkin, E. B.},
      TITLE = {Local times and quantum fields},
      BOOKTITLE = {Seminar on Stochastic Processes, 1983},
      VENUE={{G}ainesville, {F}la., 1983},
      SERIES = {Progr. Probab. Statist.},
      VOLUME = {7},
      PAGES = {69--83},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Boston, MA},
      YEAR = {1984},
      MRCLASS = {60G20 (60J55 81E08)},
      MRNUMBER = {0902412},
      ZBLNUMBER = {0554.60058},
      }
  • [Eisenbaum95] Go to document N. Eisenbaum, "Une version sans conditionnement du théorème d’isomorphisms de Dynkin," in Séminaire de Probabilités, XXIX, New York: Springer-Verlag, 1995, vol. 1613, pp. 266-289.
    @incollection {Eisenbaum95, MRKEY = {1459468},
      AUTHOR = {Eisenbaum, Nathalie},
      TITLE = {Une version sans conditionnement du théorème d'isomorphisms de {D}ynkin},
      BOOKTITLE = {Séminaire de {P}robabilités, {XXIX}},
      SERIES = {Lecture Notes in Math.},
      VOLUME = {1613},
      PAGES = {266--289},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1995},
      MRCLASS = {60J55 (60G15 60J25 60J65)},
      MRNUMBER = {1459468},
      MRREVIEWER = {Haya Kaspi},
      DOI = {10.1007/BFb0094219},
      ZBLNUMBER = {0849.60075},
      }
  • [EKMRS00] Go to document N. Eisenbaum, H. Kaspi, M. B. Marcus, J. Rosen, and Z. Shi, "A Ray-Knight theorem for symmetric Markov processes," Ann. Probab., vol. 28, iss. 4, pp. 1781-1796, 2000.
    @article {EKMRS00, MRKEY = {1813843},
      AUTHOR = {Eisenbaum, Nathalie and Kaspi, Haya and Marcus, Michael B. and Rosen, Jay and Shi, Zhan},
      TITLE = {A {R}ay-{K}night theorem for symmetric {M}arkov processes},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {28},
      YEAR = {2000},
      NUMBER = {4},
      PAGES = {1781--1796},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60J55},
      MRNUMBER = {1813843},
      MRREVIEWER = {Joanna B. Mitro},
      DOI = {10.1214/aop/1019160507},
      ZBLNUMBER = {1044.60064},
      }
  • [Feige95b] Go to document U. Feige, "A tight lower bound on the cover time for random walks on graphs," Random Structures Algorithms, vol. 6, iss. 4, pp. 433-438, 1995.
    @article {Feige95b, MRKEY = {1368844},
      AUTHOR = {Feige, Uriel},
      TITLE = {A tight lower bound on the cover time for random walks on graphs},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {6},
      YEAR = {1995},
      NUMBER = {4},
      PAGES = {433--438},
      ISSN = {1042-9832},
      MRCLASS = {60J15 (60C05)},
      MRNUMBER = {1368844},
      MRREVIEWER = {Graham Brightwell},
      DOI = {10.1002/rsa.3240060406},
      ZBLNUMBER = {0832.60016},
      }
  • [Feige95a] Go to document U. Feige, "A tight upper bound on the cover time for random walks on graphs," Random Structures Algorithms, vol. 6, iss. 1, pp. 51-54, 1995.
    @article {Feige95a, MRKEY = {1368834},
      AUTHOR = {Feige, Uriel},
      TITLE = {A tight upper bound on the cover time for random walks on graphs},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {6},
      YEAR = {1995},
      NUMBER = {1},
      PAGES = {51--54},
      ISSN = {1042-9832},
      MRCLASS = {60J15 (60C05)},
      MRNUMBER = {1368834},
      MRREVIEWER = {Graham Brightwell},
      DOI = {10.1002/rsa.3240060106},
      ZBLNUMBER = {0811.60060},
      }
  • [FZ09] U. Feige and O. Zeitouni, Deterministic approximation for the cover time of trees.
    @misc{FZ09,
      author={Feige, Uriel and Zeitouni, O.},
      TITLE={Deterministic approximation for the cover time of trees},
      NOTE={preprint},
      ARXIV={0909.2005},
     }
  • [F1] Go to document X. Fernique, "Régularité de processus gaussiens," Invent. Math., vol. 12, pp. 304-320, 1971.
    @article {F1, MRKEY = {0286166},
      AUTHOR = {Fernique, Xavier},
      TITLE = {Régularité de processus gaussiens},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {12},
      YEAR = {1971},
      PAGES = {304--320},
      ISSN = {0020-9910},
      MRCLASS = {60.40},
      MRNUMBER = {0286166},
      MRREVIEWER = {R. Theodorescu},
      ZBLNUMBER = {0217.21104},
      DOI = {10.1007/BF01403310},
     }
  • [F2] Go to document X. Fernique, "Régularité des trajectoires des fonctions aléatoires gaussiennes," in École d’Été de Probabilités de Saint-Flour, IV-1974, New York: Springer-Verlag, 1975, vol. 480, pp. 1-96.
    @incollection {F2, MRKEY = {0413238},
      AUTHOR = {Fernique, Xavier},
      TITLE = {Régularité des trajectoires des fonctions aléatoires gaussiennes},
      BOOKTITLE = {\'{E}cole d'\'{E}té de {P}robabilités de {S}aint-{F}lour, {IV}-1974},
      PAGES = {1--96},
      SERIES={Lecture Notes in Math.},
      VOLUME={480},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1975},
      MRCLASS = {60G15},
      MRNUMBER = {0413238},
      MRREVIEWER = {Michael Marcus},
      ZBLNUMBER = {0331.60025},
      DOI = {10.1007/BFb0080190},
     }
  • [Foster48] R. M. Foster, "The average impedance of an electrical network," in Reissner Anniversary Volume, Contributions to Applied Mechanics, J. W. Edwards, Ann Arbor, Michigan, 1948, pp. 333-340.
    @incollection {Foster48, MRKEY = {0029773},
      AUTHOR = {Foster, Ronald M.},
      TITLE = {The average impedance of an electrical network},
      BOOKTITLE = {Reissner {A}nniversary {V}olume, {C}ontributions to {A}pplied {M}echanics},
      PAGES = {333--340},
      PUBLISHER = {J. W. Edwards, Ann Arbor, Michigan},
      YEAR = {1948},
      MRCLASS = {78.0X},
      MRNUMBER = {0029773},
      MRREVIEWER = {N. Levinson},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {0040.41801},
      }
  • [GZ03] Go to document O. Guédon and A. Zvavitch, "Supremum of a process in terms of trees," in Geometric Aspects of Functional Analysis, New York: Springer-Verlag, 2003, vol. 1807, pp. 136-147.
    @incollection {GZ03, MRKEY = {2083394},
      AUTHOR = {Gu{é}don, Olivier and Zvavitch, Artem},
      TITLE = {Supremum of a process in terms of trees},
      BOOKTITLE = {Geometric Aspects of Functional Analysis},
      SERIES = {Lecture Notes in Math.},
      VOLUME = {1807},
      PAGES = {136--147},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2003},
      MRCLASS = {60E15 (46B20 46N30 60C05 60G15)},
      MRNUMBER = {2083394},
      MRREVIEWER = {Catherine Donati-Martin},
      ZBLNUMBER = {1038.60028},
      DOI = {10.1007/978-3-540-36428-3_12},
     }
  • [Janson97] Go to document S. Janson, Gaussian Hilbert Spaces, Cambridge: Cambridge Univ. Press, 1997, vol. 129.
    @book {Janson97, MRKEY = {1474726},
      AUTHOR = {Janson, Svante},
      TITLE = {Gaussian {H}ilbert Spaces},
      SERIES = {Cambridge Tracts in Math.},
      VOLUME = {129},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1997},
      PAGES = {x+340},
      ISBN = {0-521-56128-0},
      MRCLASS = {60G35 (60H15 62M20 81T08)},
      MRNUMBER = {1474726},
      MRREVIEWER = {Amarjit Budhiraja},
      DOI = {10.1017/CBO9780511526169},
      ZBLNUMBER = {0887.60009},
      }
  • [JS00] Go to document J. Jonasson and O. Schramm, "On the cover time of planar graphs," Electron. Comm. Probab., vol. 5, pp. 85-90, 2000.
    @article {JS00, MRKEY = {1781842},
      AUTHOR = {Jonasson, Johan and Schramm, Oded},
      TITLE = {On the cover time of planar graphs},
      JOURNAL = {Electron. Comm. Probab.},
      FJOURNAL = {Electronic Communications in Probability},
      VOLUME = {5},
      YEAR = {2000},
      PAGES = {85--90},
      ISSN = {1083-589X},
      MRCLASS = {60J10 (05C85 52C15 60G50)},
      MRNUMBER = {1781842},
      MRREVIEWER = {Robert P. Dobrow},
      DOI = {10.1214/ECP.v5-1022},
      ZBLNUMBER = {0949.60083},
      }
  • [KKLV00] Go to document J. D. Kahn, J. H. Kim, L. Lovász, and V. H. Vu, "The cover time, the blanket time, and the Matthews bound," in 41st Annual Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Comput. Soc. Press, 2000, pp. 467-475.
    @incollection {KKLV00, MRKEY = {1931843},
      AUTHOR = {Kahn, Jeff D. and Kim, J. H. and Lov{á}sz, L. and Vu, V. H.},
      TITLE = {The cover time, the blanket time, and the {M}atthews bound},
      BOOKTITLE = {41st {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience},
      VENUE={{R}edondo {B}each, {CA},
      2000},
      PAGES = {467--475},
      PUBLISHER = {IEEE Comput. Soc. Press},
      ADDRESS = {Los Alamitos, CA},
      YEAR = {2000},
      MRCLASS = {68W25 (90C35)},
      MRNUMBER = {1931843},
      DOI = {10.1109/SFCS.2000.892134},
      }
  • [KLNS89] Go to document J. D. Kahn, N. Linial, N. Nisan, and M. E. Saks, "On the cover time of random walks on graphs," J. Theoret. Probab., vol. 2, iss. 1, pp. 121-128, 1989.
    @article {KLNS89, MRKEY = {0981769},
      AUTHOR = {Kahn, Jeff D. and Linial, Nathan and Nisan, Noam and Saks, Michael E.},
      TITLE = {On the cover time of random walks on graphs},
      JOURNAL = {J. Theoret. Probab.},
      FJOURNAL = {Journal of Theoretical Probability},
      VOLUME = {2},
      YEAR = {1989},
      NUMBER = {1},
      PAGES = {121--128},
      ISSN = {0894-9840},
      CODEN = {JTPREO},
      MRCLASS = {60J10 (05C99)},
      MRNUMBER = {0981769},
      MRREVIEWER = {David J. Aldous},
      DOI = {10.1007/BF01048274},
      ZBLNUMBER = {0681.60064},
      }
  • [KR93] Go to document D. J. Klein and M. Randić, "Resistance distance," J. Math. Chem., vol. 12, iss. 1-4, pp. 81-95, 1993.
    @article {KR93, MRKEY = {1219566},
      AUTHOR = {Klein, D. J. and Randi{ć},
      M.},
      TITLE = {Resistance distance},
      NOTE = {Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991)},
      JOURNAL = {J. Math. Chem.},
      FJOURNAL = {Journal of Mathematical Chemistry},
      VOLUME = {12},
      YEAR = {1993},
      NUMBER = {1-4},
      PAGES = {81--95},
      ISSN = {0259-9791},
      CODEN = {JMCHEG},
      MRCLASS = {94C15},
      MRNUMBER = {1219566},
      MRREVIEWER = {Andr{á}s Recski},
      DOI = {10.1007/BF01164627},
      }
  • [Knight63] F. B. Knight, "Random walks and a sojourn density process of Brownian motion," Trans. Amer. Math. Soc., vol. 109, pp. 56-86, 1963.
    @article {Knight63, MRKEY = {0154337},
      AUTHOR = {Knight, F. B.},
      TITLE = {Random walks and a sojourn density process of {B}rownian motion},
      JOURNAL = {Trans. Amer. Math. Soc.},
      FJOURNAL = {Transactions of the American Mathematical Society},
      VOLUME = {109},
      YEAR = {1963},
      PAGES = {56--86},
      ISSN = {0002-9947},
      MRCLASS = {60.66 (60.62)},
      MRNUMBER = {0154337},
      MRREVIEWER = {H. P. McKean, Jr.},
      ZBLNUMBER = {0119.14604},
      }
  • [Ledoux89] M. Ledoux, The Concentration of Measure Phenomenon, Providence, RI: Amer. Math. Soc., 2001.
    @book {Ledoux89, MRKEY = {1849347},
      AUTHOR = {Ledoux, Michel},
      TITLE = {The Concentration of Measure Phenomenon},
      SERIES = {Math. Surveys Monogr.},
      NUMBER = {89},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, RI},
      YEAR = {2001},
      PAGES = {x+181},
      ISBN = {0-8218-2864-9},
      MRCLASS = {28C15 (28A35 46B09 60E15 82B44)},
      MRNUMBER = {1849347},
      MRREVIEWER = {Werner Linde},
      ZBLNUMBER = {0995.60002},
      }
  • [LT91] M. Ledoux and M. Talagrand, Probability in Banach Spaces, New York: Springer-Verlag, 1991, vol. 23.
    @book {LT91, MRKEY = {1102015},
      AUTHOR = {Ledoux, Michel and Talagrand, Michel},
      TITLE = {Probability in {B}anach Spaces},
      SERIES = {Ergeb. Math. Grenzgeb.},
      VOLUME = {23},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1991},
      PAGES = {xii+480},
      ISBN = {3-540-52013-9},
      MRCLASS = {60-02 (60Bxx 60Fxx 60Gxx)},
      MRNUMBER = {1102015},
      MRREVIEWER = {Evarist Gin{é}},
      ZBLNUMBER = {0748.60004},
      }
  • [LPW09] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing Times, Providence, RI: Amer. Math. Soc., 2009.
    @book {LPW09, MRKEY = {2466937},
      AUTHOR = {Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L.},
      TITLE = {Markov Chains and Mixing Times},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, RI},
      YEAR = {2009},
      PAGES = {xviii+371},
      ISBN = {978-0-8218-4739-8},
      MRCLASS = {60J10 (60-01 60J05 60K35 60K37 68U20 68W20)},
      MRNUMBER = {2466937},
      MRREVIEWER = {Olle H{ä}ggstr{ö}m},
      ZBLNUMBER = {1160.60001},
      }
  • [Lov96] L. Lovász, "Random walks on graphs: a survey," in Combinatorics, Paul Erdős is Eighty, Vol. 2, Budapest: János Bolyai Math. Soc., 1996, vol. 2, pp. 353-397.
    @incollection {Lov96, MRKEY = {1395866},
      AUTHOR = {Lov{á}sz, L.},
      TITLE = {Random walks on graphs: a survey},
      BOOKTITLE = {Combinatorics, {P}aul {E}rdős is Eighty, {V}ol. 2},
      VENUE={{K}eszthely, 1993},
      SERIES = {Bolyai Soc. Math. Stud.},
      VOLUME = {2},
      PAGES = {353--397},
      PUBLISHER = {János Bolyai Math. Soc.},
      ADDRESS = {Budapest},
      YEAR = {1996},
      MRCLASS = {60J15 (05C50 05C99)},
      MRNUMBER = {1395866},
      ZBLNUMBER = {0854.60071},
      }
  • [Lyons92] Go to document R. Lyons, "Random walks, capacity and percolation on trees," Ann. Probab., vol. 20, iss. 4, pp. 2043-2088, 1992.
    @article {Lyons92, MRKEY = {1188053},
      AUTHOR = {Lyons, Russell},
      TITLE = {Random walks, capacity and percolation on trees},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {20},
      YEAR = {1992},
      NUMBER = {4},
      PAGES = {2043--2088},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60J15 (60K35 82B41 82B43)},
      MRNUMBER = {1188053},
      MRREVIEWER = {Robin Pemantle},
      DOI = {10.1214/aop/1176989540},
      ZBLNUMBER = {0766.60091},
      }
  • [LP] Go to document R. Lyons and Y. Peres, Probability on Trees and Networks, 2009.
    @misc{LP,
      author = {Lyons, Russell and Peres, Y.},
      TITLE = {Probability on Trees and Networks},
      NOTE={in preparation},
      URL={http://mypage.iu.edu/~rdlyons/prbtree/book.pdf},
      YEAR={2009},
     }
  • [MR92] Go to document M. B. Marcus and J. Rosen, "Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes," Ann. Probab., vol. 20, iss. 4, pp. 1603-1684, 1992.
    @article {MR92, MRKEY = {1188037},
      AUTHOR = {Marcus, Michael B. and Rosen, Jay},
      TITLE = {Sample path properties of the local times of strongly symmetric {M}arkov processes via {G}aussian processes},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {20},
      YEAR = {1992},
      NUMBER = {4},
      PAGES = {1603--1684},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60G15 (60J25 60J55)},
      MRNUMBER = {1188037},
      MRREVIEWER = {Robert J. Adler},
      DOI = {10.1214/aop/1176989524},
      ZBLNUMBER = {0762.60068},
      }
  • [MR01] M. B. Marcus and J. Rosen, "Gaussian processes and local times of symmetric Lévy processes," in Lévy Processes, Boston, MA: Birkhäuser, 2001, pp. 67-88.
    @incollection {MR01, MRKEY = {1833693},
      AUTHOR = {Marcus, Michael B. and Rosen, Jay},
      TITLE = {Gaussian processes and local times of symmetric {L}évy processes},
      BOOKTITLE = {Lévy Processes},
      PAGES = {67--88},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Boston, MA},
      YEAR = {2001},
      MRCLASS = {60J55 (60G15 60G51)},
      MRNUMBER = {1833693},
      MRREVIEWER = {Haya Kaspi},
      ZBLNUMBER = {0988.60026},
      }
  • [MR06] Go to document M. B. Marcus and J. Rosen, Markov Processes, Gaussian Processes, and Local Times, Cambridge: Cambridge Univ. Press, 2006, vol. 100.
    @book {MR06, MRKEY = {2250510},
      AUTHOR = {Marcus, Michael B. and Rosen, Jay},
      TITLE = {Markov Processes, {G}aussian Processes, and Local Times},
      SERIES = {Cambridge Stud. Adv. Math.},
      VOLUME = {100},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2006},
      PAGES = {x+620},
      ISBN = {978-0-521-86300-1; 0-521-86300-7},
      MRCLASS = {60-02 (60G15 60J25 60J55)},
      MRNUMBER = {2250510},
      MRREVIEWER = {Nathalie Eisenbaum},
      DOI = {10.1017/CBO9780511617997},
      ZBLNUMBER = {1129.60002},
      }
  • [Matthews88] Go to document P. Matthews, "Covering problems for Markov chains," Ann. Probab., vol. 16, iss. 3, pp. 1215-1228, 1988.
    @article {Matthews88, MRKEY = {0942764},
      AUTHOR = {Matthews, Peter},
      TITLE = {Covering problems for {M}arkov chains},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {16},
      YEAR = {1988},
      NUMBER = {3},
      PAGES = {1215--1228},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60J10},
      MRNUMBER = {0942764},
      MRREVIEWER = {Xiang Qun Yang},
      DOI = {10.1214/aop/1176991686},
      ZBLNUMBER = {0712.60076},
      }
  • [Ray63] D. Ray, "Sojourn times of diffusion processes," Illinois J. Math., vol. 7, pp. 615-630, 1963.
    @article {Ray63, MRKEY = {0156383},
      AUTHOR = {Ray, Daniel},
      TITLE = {Sojourn times of diffusion processes},
      JOURNAL = {Illinois J. Math.},
      FJOURNAL = {Illinois Journal of Mathematics},
      VOLUME = {7},
      YEAR = {1963},
      PAGES = {615--630},
      ISSN = {0019-2082},
      MRCLASS = {60.62},
      MRNUMBER = {0156383},
      MRREVIEWER = {H. P. McKean, Jr.},
      ZBLNUMBER = {0118.13403},
      }
  • [SpielmanICM] D. A. Spielman, "Algorithms, graph theory, and linear equations in Laplacian matrices," in Proceedings of the International Congress of Mathematicians. Volume IV, New Delhi, 2010, pp. 2698-2722.
    @inproceedings {SpielmanICM, MRKEY = {2827990},
      AUTHOR = {Spielman, Daniel A.},
      TITLE = {Algorithms, graph theory, and linear equations in {L}aplacian matrices},
      BOOKTITLE = {Proceedings of the {I}nternational {C}ongress of {M}athematicians. {V}olume {IV}},
      PAGES = {2698--2722},
      PUBLISHER = {Hindustan Book Agency},
      ADDRESS = {New Delhi},
      YEAR = {2010},
      MRCLASS = {68Q25 (65F05)},
      MRNUMBER = {2827990},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {05971213},
      }
  • [SS08] Go to document D. A. Spielman and N. Srivastava, "Graph sparsification by effective resistances," in STOC’08, New York: ACM, 2008, pp. 563-568.
    @incollection {SS08, MRKEY = {2582687},
      AUTHOR = {Spielman, Daniel A. and Srivastava, Nikhil},
      TITLE = {Graph sparsification by effective resistances},
      BOOKTITLE = {S{TOC}'08},
      PAGES = {563--568},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      YEAR = {2008},
      MRCLASS = {05C85 (68P05 68R10)},
      MRNUMBER = {2582687},
      DOI = {10.1145/1374376.1374456},
      ZBLNUMBER = {05485569},
      }
  • [ST06] D. A. Spielman and S. -H. Teng, Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems, 2006.
    @misc{ST06,
      author = {Spielman, Daniel A. and Teng, S.-H.},
      TITLE={Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems},
      ARXIV={cs/0607105},
      YEAR={2006},
     }
  • [Talagrand87] Go to document M. Talagrand, "Regularity of gaussian processes," Acta Math., vol. 159, iss. 1-2, pp. 99-149, 1987.
    @article {Talagrand87, MRKEY = {0906527},
      AUTHOR = {Talagrand, Michel},
      TITLE = {Regularity of gaussian processes},
      JOURNAL = {Acta Math.},
      FJOURNAL = {Acta Mathematica},
      VOLUME = {159},
      YEAR = {1987},
      NUMBER = {1-2},
      PAGES = {99--149},
      ISSN = {0001-5962},
      CODEN = {ACMAA8},
      MRCLASS = {60G15},
      MRNUMBER = {0906527},
      MRREVIEWER = {Michael Marcus},
      DOI = {10.1007/BF02392556},
      ZBLNUMBER = {0712.60044},
      }
  • [Talagrand95a] M. Talagrand, "Embedding subspaces of $L_p$ in $l^N_p$," in Geometric Aspects of Functional Analysis, Basel: Birkhäuser, 1995, vol. 77, pp. 311-325.
    @incollection {Talagrand95a, MRKEY = {1353469},
      AUTHOR = {Talagrand, Michel},
      TITLE = {Embedding subspaces of {$L\sb p$} in {$l\sp N\sb p$}},
      BOOKTITLE = {Geometric Aspects of Functional Analysis},
      VENUE={{I}srael, 1992--1994},
      SERIES = {Oper. Theory Adv. Appl.},
      VOLUME = {77},
      PAGES = {311--325},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Basel},
      YEAR = {1995},
      MRCLASS = {46B07 (46B20 46E30)},
      MRNUMBER = {1353469},
      MRREVIEWER = {Wolfgang Lusky},
      ZBLNUMBER = {0828.46011},
      }
  • [Talagrand96] Go to document M. Talagrand, "Majorizing measures: the generic chaining," Ann. Probab., vol. 24, iss. 3, pp. 1049-1103, 1996.
    @article {Talagrand96, MRKEY = {1411488},
      AUTHOR = {Talagrand, Michel},
      TITLE = {Majorizing measures: the generic chaining},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {24},
      YEAR = {1996},
      NUMBER = {3},
      PAGES = {1049--1103},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60G05 (46N30 47N30 60G15)},
      MRNUMBER = {1411488},
      MRREVIEWER = {Werner Linde},
      DOI = {10.1214/aop/1065725175},
      ZBLNUMBER = {0867.60017},
      }
  • [Tala01] Go to document M. Talagrand, "Majorizing measures without measures," Ann. Probab., vol. 29, iss. 1, pp. 411-417, 2001.
    @article {Tala01, MRKEY = {1825156},
      AUTHOR = {Talagrand, Michel},
      TITLE = {Majorizing measures without measures},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {29},
      YEAR = {2001},
      NUMBER = {1},
      PAGES = {411--417},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60G15 (60G17 60G60)},
      MRNUMBER = {1825156},
      MRREVIEWER = {Werner Linde},
      DOI = {10.1214/aop/1008956336},
      ZBLNUMBER = {1019.60033},
      }
  • [Talagrand05] M. Talagrand, The Generic Chaining. Upper and Lower Bounds of Stochastic Processes, New York: Springer-Verlag, 2005.
    @book {Talagrand05, MRKEY = {2133757},
      AUTHOR = {Talagrand, Michel},
      TITLE = {The Generic Chaining. Upper and Lower Bounds of Stochastic Processes},
      SERIES = {Springer Monogr. Math.},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2005},
      PAGES = {viii+222},
      ISBN = {3-540-24518-9},
      MRCLASS = {60-02 (46B09 46B20 46N30 60D05 60G15 60G17 60G52)},
      MRNUMBER = {2133757},
      MRREVIEWER = {Werner Linde},
      ZBLNUMBER = {1075.60001},
      }
  • [Tetali91] Go to document P. Tetali, "Random walks and the effective resistance of networks," J. Theoret. Probab., vol. 4, iss. 1, pp. 101-109, 1991.
    @article {Tetali91, MRKEY = {1088395},
      AUTHOR = {Tetali, Prasad},
      TITLE = {Random walks and the effective resistance of networks},
      JOURNAL = {J. Theoret. Probab.},
      FJOURNAL = {Journal of Theoretical Probability},
      VOLUME = {4},
      YEAR = {1991},
      NUMBER = {1},
      PAGES = {101--109},
      ISSN = {0894-9840},
      CODEN = {JTPREO},
      MRCLASS = {60J15 (94C15)},
      MRNUMBER = {1088395},
      MRREVIEWER = {Carsten Thomassen},
      DOI = {10.1007/BF01046996},
      ZBLNUMBER = {0722.60070},
      }
  • [WZ96] P. Winkler and D. Zuckerman, "Multiple cover time," Random Structures Algorithms, vol. 9, iss. 4, pp. 403-411, 1996.
    @article {WZ96, MRKEY = {1605407},
      AUTHOR = {Winkler, Peter and Zuckerman, David},
      TITLE = {Multiple cover time},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {9},
      YEAR = {1996},
      NUMBER = {4},
      PAGES = {403--411},
      ISSN = {1042-9832},
      MRCLASS = {60J15 (05C99 60C05)},
      MRNUMBER = {1605407},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1002/(SICI)1098-2418(199612)9:4<403::AID-RSA4>3.0.CO;2-0},
      ZBLNUMBER = {0872.60054},
      }
  • [Zuckerman92] Go to document D. Zuckerman, "A technique for lower bounding the cover time," SIAM J. Discrete Math., vol. 5, iss. 1, pp. 81-87, 1992.
    @article {Zuckerman92, MRKEY = {1146899},
      AUTHOR = {Zuckerman, David},
      TITLE = {A technique for lower bounding the cover time},
      JOURNAL = {SIAM J. Discrete Math.},
      FJOURNAL = {SIAM Journal on Discrete Mathematics},
      VOLUME = {5},
      YEAR = {1992},
      NUMBER = {1},
      PAGES = {81--87},
      ISSN = {0895-4801},
      CODEN = {SJDMEC},
      MRCLASS = {60J15},
      MRNUMBER = {1146899},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1137/0405007},
      ZBLNUMBER = {0743.60068},
      }

Authors

Jian Ding

University of California at Berkeley, Berkeley, CA

Current address:

Department of Mathematics
Building 380
Stanford University
Stanford, CA 94305 James R. Lee

Department of Computer Science and Engineering
Box 352350,br/>University of Washington
Seattle, WA 98195-2350

Yuval Peres

Microsoft Research
One Microsoft Way
Redmond, WA