Tight bounds for the cover time of multiple random walks

M. Adler, E. Halperin, R. Karp, V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, in: 35th Annual ACM Symposium on Theory of Computing, STOC’03, 2003, pp. 575–584. D. Aldous, J. Fill, Reversible Markov Chains and Random Walks on Graphs, 2002 (in preparation). Draft available at http://www.stat.berkeley.edu/~aldous/RWG/book.html. Aldous, 1983, On the time taken by random walks on finite groups to visit every state, Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 62, 361, 10.1007/BF00535260 R. Aleliunas, R. Karp, R. Lipton, L. Lovász, C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, in: 20th Annual IEEE Symposium on Foundations of Computer Science, FOCS’79, 1979, pp. 218–223. N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, M. Tuttle, Many random walks are faster than one, in: 20th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA’08, 2008, pp. 119–128. L. Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, in: 23rd Annual ACM Symposium on Theory of Computing, STOC’91, 1991, pp. 164–174. P. Berenbrink, C. Cooper, R. Elsässer, T. Radzik, T. Sauerwald, Speeding up random walks with neighborhood exploration, in: 21th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA’10, 2010, pp. 1422–1435. Broder, 1989, Bounds on the cover time, Journal of Theoretical Probability, 2, 101, 10.1007/BF01048273 Broder, 1994, Trading space for time in undirected s–t connectivity, SIAM Journal on Computing, 23, 324, 10.1137/S0097539790190144 Carne, 1985, A transmutation formula for Markov chains, Bulletin des Sciences Mathematiques, 109, 399 Chandra, 1997, The electrical resistance of a graph captures its commute and cover times, Computational Complexity, 6, 312, 10.1007/BF01270385 Cooper, 2007, The cover time of sparse random graphs, Random Structures and Algorithms, 30, 1, 10.1002/rsa.20151 C. Cooper, A. Frieze, T. Radzik, Multiple random walks and interacting particle systems, in: 36th International Colloquium on Automata, Languages, and Programming, ICALP’09, 2009, pp. 399–410. A. Czumaj, C. Sohler, Testing expansion in bounded-degree graphs, in: 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS’07, 2007, pp. 570–578. Diaconis, 1993, Comparison theorems for reversible markov chains, The Annals of Applied Probability, 2, 696, 10.1214/aoap/1177005359 Diaconis, 1990, Asymptotic analysis of a random walk on a hypercube with many dimensions, Random Structures and Algorithms, 1, 51, 10.1002/rsa.3240010105 N.B. Dimitrov, C.G. Plaxton, Optimal cover time for a graph-based coupon collector process, in: 32nd International Colloquium on Automata, Languages, and Programming, ICALP’05, 2005, pp. 702–716. K. Efremenko, O. Reingold, How well do random walks parallelize? in: 13th International Workshop on Randomization and Computation, RANDOM’09, 2009, pp. 476–489. R. Elsässer, T. Sauerwald, Tight bounds for the cover time of multiple random walks, in: 36th International Colloquium on Automata, Languages, and Programming, ICALP’09, 2009, pp. 415–426. Erdős, 1959, On random graphs, Publicationes Mathematicae Debrecen, 6, 290, 10.5486/PMD.1959.6.3-4.12 Feige, 1995, A tight lower bound for the cover time of random walks on graphs, Random Structures and Algorithms, 6, 433, 10.1002/rsa.3240060406 Feige, 1995, A tight upper bound for the cover time of random walks on graphs, Random Structures and Algorithms, 6, 51, 10.1002/rsa.3240060106 S. Ikeda, I. Kubo, N. Okumoto, M. Yamashita, Impact of local topological information on random walks on finite graphs, in: 30st International Colloquium on Automata, Languages, and Programming, ICALP’03, 2003, pp. 1054–1067. S. Kale, C. Seshadhri, Property testing on k-vertex-connectivity of graphs, in: 35th International Colloquium on Automata, Languages, and Programming, ICALP’08, 2008, pp. 527–538. Lovász, 1993, Random walks on graphs: a survey, Combinatorics, 2, 1 Matthews, 1988, Covering problems for Brownian motion on spheres, Annals of Probability, 16, 189, 10.1214/aop/1176991894 McDiarmid, 1989, On the method of bounded differences, vol. 141, 148 Sinclair, 1992, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combinatorics, Probability & Computing, 1, 351, 10.1017/S0963548300000390 Sinclair, 1993 Zuckerman, 1992, A technique for lower bounding the cover time, SIAM Journal on Discrete Mathematics, 5, 81, 10.1137/0405007