{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:34:31Z","timestamp":1782970471017,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Swiss NSF","award":["P2ELP2_181772"],"award-info":[{"award-number":["P2ELP2_181772"]}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["772346"],"award-info":[{"award-number":["772346"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384303","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"364-377","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Walking randomly, massively, and efficiently"],"prefix":"10.1145","author":[{"given":"Jakub","family":"\u0141\u0105cki","sequence":"first","affiliation":[{"name":"Google Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Slobodan","family":"Mitrovi\u0107","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krzysztof","family":"Onak","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. 475\u2013486","author":"Andersen Reid","unstructured":"Reid Andersen , Fan R. K. Chung , and Kevin J. Lang . 2006. Local Graph Partitioning using PageRank Vectors . In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. 475\u2013486 . Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. 2006. Local Graph Partitioning using PageRank Vectors. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. 475\u2013486."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_4_1","volume-title":"Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. 1616\u20131635","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi , MohammadHossein Bateni , Aaron Bernstein , Vahab Mirrokni , and Cliff Stein . 2019 . Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. 1616\u20131635 . Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. 2019. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. 1616\u20131635."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310483"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Soheil Behnezhad Laxman Dhulipala Hossein Esfandiari Jakub \u0141\u0105cki and Vahab Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. FOCS.  Soheil Behnezhad Laxman Dhulipala Hossein Esfandiari Jakub \u0141\u0105cki and Vahab Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. FOCS.","DOI":"10.1109\/FOCS.2019.00095"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Soheil Behnezhad MohammadTaghi Hajiaghayi and David G Harris. 2019. Exponentially Faster Massively Parallel Maximal Matching. FOCS.  Soheil Behnezhad MohammadTaghi Hajiaghayi and David G Harris. 2019. Exponentially Faster Massively Parallel Maximal Matching. FOCS.","DOI":"10.1109\/FOCS.2019.00096"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129098"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30541-2_4"},{"key":"e_1_3_2_1_14_1","unstructured":"Sebastian Brandt Manuela Fischer and Jara Uitto. 2018. Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. arXiv preprint arXiv:1807.05374.  Sebastian Brandt Manuela Fischer and Jara Uitto. 2018. Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. arXiv preprint arXiv:1807.05374."},{"key":"e_1_3_2_1_15_1","volume-title":"Sublinear Algorithms for Local Graph Centrality Estimation. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018","author":"Bressan Marco","year":"2018","unstructured":"Marco Bressan , Enoch Peserico , and Luca Pretto . 2018 . Sublinear Algorithms for Local Graph Centrality Estimation. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018 , Paris, France , October 7-9, 2018. 709\u2013718. Marco Bressan, Enoch Peserico, and Luca Pretto. 2018. Sublinear Algorithms for Local Graph Centrality Estimation. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018. 709\u2013718."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063670"},{"key":"e_1_3_2_1_17_1","unstructured":"LA Breyer. 2002. Markovian page ranking distributions: some theory and simulations.  LA Breyer. 2002. Markovian page ranking distributions: some theory and simulations."},{"key":"e_1_3_2_1_18_1","volume-title":"The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30, 1-7","author":"Brin Sergey","year":"1998","unstructured":"Sergey Brin and Lawrence Page . 1998. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30, 1-7 ( 1998 ), 107\u2013117. Sergey Brin and Lawrence Page. 1998. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30, 1-7 (1998), 107\u2013117."},{"key":"e_1_3_2_1_19_1","volume-title":"DISC 2016, Paris, France, September 27-29, 2016. Proceedings. 43\u201356","author":"Censor-Hillel Keren","year":"2016","unstructured":"Keren Censor-Hillel , Eldar Fischer , Gregory Schwartzman , and Yadu Vasudev . 2016 . Fast Distributed Algorithms for Testing Graph Properties. In Distributed Computing - 30th International Symposium , DISC 2016, Paris, France, September 27-29, 2016. Proceedings. 43\u201356 . Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. 2016. Fast Distributed Algorithms for Testing Graph Properties. In Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings. 43\u201356."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031248"},{"key":"e_1_3_2_1_21_1","volume-title":"Testing Graph Clusterability: Algorithms and Lower Bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 497\u2013508","author":"Chiplunkar A.","unstructured":"A. Chiplunkar , M. Kapralov , S. Khanna , A. Mousavifar , and Y. Peres . 2018 . Testing Graph Clusterability: Algorithms and Lower Bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 497\u2013508 . A. Chiplunkar, M. Kapralov, S. Khanna, A. Mousavifar, and Y. Peres. 2018. Testing Graph Clusterability: Algorithms and Lower Bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 497\u2013508."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Artur Czumaj Morteza Monemizadeh Krzysztof Onak and Christian Sohler. 2019. Planar graphs: Random walks and bipartiteness testing. Random Structures & Algorithms.  Artur Czumaj Morteza Monemizadeh Krzysztof Onak and Christian Sohler. 2019. Planar graphs: Random walks and bipartiteness testing. Random Structures & Algorithms.","DOI":"10.1002\/rsa.20826"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746618"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831000012X"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970397"},{"key":"e_1_3_2_1_27_1","volume-title":"Gopal Pandurangan, and Eli Upfal.","author":"Sarma Atish Das","year":"2015","unstructured":"Atish Das Sarma , Anisur Rahaman Molla , Gopal Pandurangan, and Eli Upfal. 2015 . Fast Distributed PageRank Computation. Theor. Comput. Sci., 561, PB ( 2015), Jan., 113\u2013121. issn:0304-3975 Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, and Eli Upfal. 2015. Fast Distributed PageRank Computation. Theor. Comput. Sci., 561, PB (2015), Jan., 113\u2013121. issn:0304-3975"},{"key":"e_1_3_2_1_28_1","article-title":"Distributed Random Walks","volume":"60","author":"Sarma Atish Das","year":"2013","unstructured":"Atish Das Sarma , Danupon Nanongkai , Gopal Pandurangan , and Prasad Tetali . 2013 . Distributed Random Walks . J. ACM , 60 , 1 (2013), 2:1\u20132:31. Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. 2013. Distributed Random Walks. J. ACM, 60, 1 (2013), 2:1\u20132:31.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129108"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IADCC.2009.4809246"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Buddhima Gamlath Sagar Kale Slobodan Mitrovi\u0107 and Ola Svensson. 2018. Weighted Matchings via Unweighted Augmentations. arXiv preprint arXiv:1811.02760.  Buddhima Gamlath Sagar Kale Slobodan Mitrovi\u0107 and Ola Svensson. 2018. Weighted Matchings via Unweighted Augmentations. arXiv preprint arXiv:1811.02760.","DOI":"10.1145\/3293611.3331603"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari Fabian Kuhn and Jara Uitto. 2019. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. FOCS.  Mohsen Ghaffari Fabian Kuhn and Jara Uitto. 2019. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. FOCS.","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_1_34_1","volume-title":"Improved Parallel Algorithms for Density-Based Network Clustering. In International Conference on Machine Learning. 2201\u20132210","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari , Silvio Lattanzi , and Slobodan Mitrovi\u0107 . 2019 . Improved Parallel Algorithms for Density-Based Network Clustering. In International Conference on Machine Learning. 2201\u20132210 . Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovi\u0107. 2019. Improved Parallel Algorithms for Density-Based Network Clustering. In International Conference on Machine Learning. 2201\u20132210."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/100812513"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0078"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/313852.314099"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210386"},{"key":"e_1_3_2_1_42_1","unstructured":"Mark Jerrum and Alistair Sinclair. 1996. The Markov chain Monte Carlo method: an approach to approximate counting and integration. Approximation algorithms for NP-hard problems 482\u2013520.  Mark Jerrum and Alistair Sinclair. 1996. The Markov chain Monte Carlo method: an approach to approximate counting and integration. Approximation algorithms for NP-hard problems 482\u2013520."},{"key":"e_1_3_2_1_43_1","volume-title":"Simulating Random Walks on Graphs in the Streaming Model. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019","author":"Jin Ce","year":"2019","unstructured":"Ce Jin . 2019 . Simulating Random Walks on Graphs in the Streaming Model. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019 , January 10-12, 2019, San Diego, California, USA. 46:1\u201346:15. Ce Jin. 2019. Simulating Random Walks on Graphs in the Streaming Model. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA. 46:1\u201346:15."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/100802980"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979325247X"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"e_1_3_2_1_48_1","volume-title":"Faster Generation of Random Spanning Trees. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27","author":"Jonathan","year":"2009","unstructured":"Jonathan A. Kelner and Aleksander M\u0105dry. 2009 . Faster Generation of Random Spanning Trees. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27 , 2009 , Atlanta, Georgia, USA. 13\u201321. Jonathan A. Kelner and Aleksander M\u0105dry. 2009. Faster Generation of Random Spanning Trees. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA. 13\u201321."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129091"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014496"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.09.002"},{"key":"e_1_3_2_1_53_1","unstructured":"Krzysztof Onak. 2018. Round compression for parallel graph algorithms in strongly sublinear space. arXiv preprint arXiv:1807.08745.  Krzysztof Onak. 2018. Round compression for parallel graph algorithms in strongly sublinear space. arXiv preprint arXiv:1807.08745."},{"key":"e_1_3_2_1_54_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web.. Stanford InfoLab.  Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web.. Stanford InfoLab."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.9"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232536"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":56,"alternative-id":["10.1145\/3357713.3384303","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384303","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}