{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:00:16Z","timestamp":1761292816312,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993646","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"61-70","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Cover times, blanket times, and majorizing measures"],"prefix":"10.1145","author":[{"given":"Jian","family":"Ding","sequence":"first","affiliation":[{"name":"U. C. Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James R.","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Peres","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, Uae"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"David Aldous and James Fill. Reversible Markov Chains and Random Walks on Graphs. In preparation available at http:\/\/www.stat.berkeley.edu\/\\verb| |aldous\/.  David Aldous and James Fill. Reversible Markov Chains and Random Walks on Graphs. In preparation available at http:\/\/www.stat.berkeley.edu\/\\verb| |aldous\/."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(82)90016-3"},{"key":"e_1_3_2_2_4_1","series-title":"Applied Mathematical Sciences","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6283-9","volume-title":"Probability approximations via the Poisson clumping heuristic","author":"Aldous David","year":"1989","unstructured":"David Aldous . Probability approximations via the Poisson clumping heuristic , volume 77 of Applied Mathematical Sciences . Springer-Verlag , New York , 1989 . David Aldous. Probability approximations via the Poisson clumping heuristic, volume 77 of Applied Mathematical Sciences. Springer-Verlag, New York, 1989."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(91)90149-T"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01047002"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000489"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/3213469"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048273"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v32:4"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270385"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.433"},{"key":"e_1_3_2_2_14_1","series-title":"Carus Mathematical Monographs","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440222","volume-title":"Random walks and electric networks","author":"Doyle Peter G.","year":"1984","unstructured":"Peter G. Doyle and J. Laurie Snell . Random walks and electric networks , volume 22 of Carus Mathematical Monographs . Mathematical Association of America , Washington, DC , 1984 . Peter G. Doyle and J. Laurie Snell. Random walks and electric networks, volume 22 of Carus Mathematical Monographs. Mathematical Association of America, Washington, DC, 1984."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(67)90017-1"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(84)90004-1"},{"key":"e_1_3_2_2_17_1","series-title":"Progr","first-page":"69","volume-title":"Seminar on stochastic processes","author":"Dynkin E. B.","year":"1983","unstructured":"E. B. Dynkin . Local times and quantum fields . In Seminar on stochastic processes , 1983 (Gainesville, Fla ., 1983), volume 7 of Progr . Probab. Statist., pages 69 -- 83 . Birkh\u00e4user Boston , Boston, MA, 1984. E. B. Dynkin. Local times and quantum fields. In Seminar on stochastic processes, 1983 (Gainesville, Fla., 1983), volume 7 of Progr. Probab. Statist., pages 69--83. Birkh\u00e4user Boston, Boston, MA, 1984."},{"key":"e_1_3_2_2_18_1","series-title":"Lecture Notes in Math","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/BFb0094219","volume-title":"S\u00e9minaire de Probabilit\u00e9s, XXIX","author":"Eisenbaum Nathalie","year":"1995","unstructured":"Nathalie Eisenbaum . Une version sans conditionnement du th\u00e9or\u00e8me d'isomorphisms de Dynkin . In S\u00e9minaire de Probabilit\u00e9s, XXIX , volume 1613 of Lecture Notes in Math ., pages 266 -- 289 . Springer , Berlin , 1995 . Nathalie Eisenbaum. Une version sans conditionnement du th\u00e9or\u00e8me d'isomorphisms de Dynkin. In S\u00e9minaire de Probabilit\u00e9s, XXIX, volume 1613 of Lecture Notes in Math., pages 266--289. Springer, Berlin, 1995."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1019160507"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060406"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060106"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01403310"},{"key":"e_1_3_2_2_23_1","first-page":"1","volume-title":"IV-1974","author":"Fernique X.","year":"1975","unstructured":"X. Fernique . Regularit\u00e9 des trajectoires des fonctions al\u00e9atoires gaussiennes. In \u00c9cole d\u2019\u00c9t\u00e9 de Probabilit\u00e9s de Saint-Flour , IV-1974 , pages 1 -- 96 . Lecture Notes in Math., Vol. 480 . Springer , Berlin, 1975 . X. Fernique. Regularit\u00e9 des trajectoires des fonctions al\u00e9atoires gaussiennes. In \u00c9cole d\u2019\u00c9t\u00e9 de Probabilit\u00e9s de Saint-Flour, IV-1974, pages 1--96. Lecture Notes in Math., Vol. 480. Springer, Berlin, 1975."},{"key":"e_1_3_2_2_24_1","first-page":"333","volume-title":"Reissner Anniversary Volume, Contributions to Applied Mechanics","author":"Foster Ronald M.","year":"1948","unstructured":"Ronald M. Foster . The average impedance of an electrical network . In Reissner Anniversary Volume, Contributions to Applied Mechanics , pages 333 -- 340 . J. W. Edwards, Ann Arbor , Michigan , 1948 . Ronald M. Foster. The average impedance of an electrical network. In Reissner Anniversary Volume, Contributions to Applied Mechanics, pages 333--340. J. W. Edwards, Ann Arbor, Michigan, 1948."},{"key":"e_1_3_2_2_25_1","unstructured":"Uriel Feige and Ofer Zeitouni. Deterministic approximation for the cover time of trees. Preprint available at http:\/\/arxiv1.library.cornell.edu\/abs\/0909.2005 .  Uriel Feige and Ofer Zeitouni. Deterministic approximation for the cover time of trees. Preprint available at http:\/\/arxiv1.library.cornell.edu\/abs\/0909.2005 ."},{"key":"e_1_3_2_2_26_1","series-title":"Lecture Notes in Math","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/978-3-540-36428-3_12","volume-title":"Geometric aspects of functional analysis","author":"Gu\u00e9don Olivier","year":"2003","unstructured":"Olivier Gu\u00e9don and Artem Zvavitch . Supremum of a process in terms of trees . In Geometric aspects of functional analysis , volume 1807 of Lecture Notes in Math ., pages 136 -- 147 . Springer , Berlin , 2003 . Olivier Gu\u00e9don and Artem Zvavitch. Supremum of a process in terms of trees. In Geometric aspects of functional analysis, volume 1807 of Lecture Notes in Math., pages 136--147. Springer, Berlin, 2003."},{"key":"e_1_3_2_2_27_1","series-title":"Cambridge Tracts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511526169","volume-title":"Gaussian Hilbert spaces","author":"Janson Svante","year":"1997","unstructured":"Svante Janson . Gaussian Hilbert spaces , volume 129 of Cambridge Tracts in Mathematics . Cambridge University Press , Cambridge , 1997 . Svante Janson. Gaussian Hilbert spaces, volume 129 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1997."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v5-1022"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796562"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048274"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0154337-6"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01164627"},{"key":"e_1_3_2_2_33_1","series-title":"Mathematical Surveys and Monographs","volume-title":"The concentration of measure phenomenon","author":"Ledoux Michel","year":"2001","unstructured":"Michel Ledoux . The concentration of measure phenomenon , volume 89 of Mathematical Surveys and Monographs . American Mathematical Society , Providence, RI , 2001 . Michel Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001."},{"key":"e_1_3_2_2_34_1","series-title":"Bolyai Soc","first-page":"353","volume-title":"Combinatorics, Paul Erdos is eighty","author":"Lov\u00e1sz L.","year":"1993","unstructured":"L. Lov\u00e1sz . Random walks on graphs: a survey . In Combinatorics, Paul Erdos is eighty , Vol. 2 (Keszthely, 1993 ), volume 2 of Bolyai Soc . Math. Stud., pages 353 -- 397 . J\u00e1nos Bolyai Math. Soc., Budapest , 1996. L. Lov\u00e1sz. Random walks on graphs: a survey. In Combinatorics, Paul Erdos is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 353--397. J\u00e1nos Bolyai Math. Soc., Budapest, 1996."},{"key":"e_1_3_2_2_35_1","volume-title":"Markov chains and mixing times","author":"Levin David A.","year":"2009","unstructured":"David A. Levin , Yuval Peres , and Elizabeth L. Wilmer . Markov chains and mixing times . American Mathematical Society , Providence, RI , 2009 . With a chapter by James G. Propp and David B. Wilson. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson."},{"key":"e_1_3_2_2_36_1","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)}","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-20212-4","volume-title":"Probability in Banach spaces","author":"Ledoux Michel","year":"1991","unstructured":"Michel Ledoux and Michel Talagrand . Probability in Banach spaces , volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)} . Springer-Verlag , Berlin , 1991 . Isoperimetry and processes. Michel Ledoux and Michel Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)}. Springer-Verlag, Berlin, 1991. Isoperimetry and processes."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989540"},{"key":"e_1_3_2_2_38_1","volume-title":"with Y. Peres. Probability on Trees and Networks. In preparation. Current version","author":"Lyons Russell","year":"2009","unstructured":"}LP Russell Lyons , with Y. Peres. Probability on Trees and Networks. In preparation. Current version available at http:\/\/mypage.iu.edu\/rdlyons\/prbtree\/book.pdf, 2009 . }LPRussell Lyons, with Y. Peres. Probability on Trees and Networks. In preparation. Current version available at http:\/\/mypage.iu.edu\/rdlyons\/prbtree\/book.pdf, 2009."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991686"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989524"},{"key":"e_1_3_2_2_41_1","first-page":"67","volume-title":"L\u00e9vy processes","author":"Michael","year":"2001","unstructured":"Michael B. Marcus and Jay Rosen. Gaussian processes and local times of symmetric L\u00e9vy processes . In L\u00e9vy processes , pages 67 -- 88 . Birkh\u00e4user Boston , Boston, MA , 2001 . Michael B. Marcus and Jay Rosen. Gaussian processes and local times of symmetric L\u00e9vy processes. In L\u00e9vy processes, pages 67--88. Birkh\u00e4user Boston, Boston, MA, 2001."},{"key":"e_1_3_2_2_42_1","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Gaussian processes, and local times","author":"Michael","year":"2006","unstructured":"Michael B. Marcus and Jay Rosen. Markov processes , Gaussian processes, and local times , volume 100 of Cambridge Studies in Advanced Mathematics . Cambridge University Press , Cambridge , 2006 . Michael B. Marcus and Jay Rosen. Markov processes, Gaussian processes, and local times, volume 100 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255645099"},{"key":"e_1_3_2_2_44_1","volume-title":"Proceedings of the International Congrees of Mathematicians","author":"Spielman D.","year":"2010","unstructured":"D. Spielman . Algorithms, graph theory , and linear equations in Laplacian matrices. To appear , Proceedings of the International Congrees of Mathematicians , Hyderabad, India , 2010 . D. Spielman. Algorithms, graph theory, and linear equations in Laplacian matrices. To appear, Proceedings of the International Congrees of Mathematicians, Hyderabad, India, 2010."},{"key":"e_1_3_2_2_45_1","volume-title":"Graph sparsification by effective resistances.","author":"Spielman D.","year":"2008","unstructured":"D. Spielman and N. Srivastava . Graph sparsification by effective resistances. Available at http:\/\/arxiv.org\/abs\/0803.0929, 2008 . D. Spielman and N. Srivastava. Graph sparsification by effective resistances. Available at http:\/\/arxiv.org\/abs\/0803.0929, 2008."},{"key":"e_1_3_2_2_46_1","volume-title":"Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems.","author":"Spielman D.","year":"2006","unstructured":"D. Spielman and S.-H. Teng . Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. Available at http:\/\/arxiv.org\/abs\/cs.NA\/0607105, 2006 . D. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. Available at http:\/\/arxiv.org\/abs\/cs.NA\/0607105, 2006."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392556"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01896658"},{"key":"e_1_3_2_2_49_1","series-title":"Oper","first-page":"311","volume-title":"Geometric aspects of functional analysis (Israel","author":"Talagrand M.","year":"1992","unstructured":"M. Talagrand . Embedding subspaces of Lp in l Np . In Geometric aspects of functional analysis (Israel , 1992 --1994), volume 77 of Oper . Theory Adv. Appl., pages 311 -- 325 . Birkhauser , Basel, 1995. M. Talagrand. Embedding subspaces of Lp in l Np. In Geometric aspects of functional analysis (Israel, 1992--1994), volume 77 of Oper. Theory Adv. Appl., pages 311--325. Birkhauser, Basel, 1995."},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1065725175"},{"key":"e_1_3_2_2_51_1","volume-title":"Springer Monographs in Mathematics","author":"Talagrand Michel","year":"2005","unstructured":"Michel Talagrand . The generic chaining . Springer Monographs in Mathematics . Springer-Verlag , Berlin , 2005 . Upper and lower bounds of stochastic processes. Michel Talagrand. The generic chaining. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2005. Upper and lower bounds of stochastic processes."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199612)9:4%3C403::AID-RSA4%3E3.0.CO;2-0"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405007"}],"event":{"name":"STOC'11: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"San Jose California USA","acronym":"STOC'11"},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993646","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:00:05Z","timestamp":1750244405000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":53,"alternative-id":["10.1145\/1993636.1993646","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993646","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}