{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:25Z","timestamp":1750221205159,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T00:00:00Z","timestamp":1522454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1228598, CCF-1320231, CCF-1535795, CCF-1422715, CCF-1535929"],"award-info":[{"award-number":["CNS-1228598, CCF-1320231, CCF-1535795, CCF-1422715, CCF-1535929"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>\n            Coalescing-branching random walks, or\n            <jats:italic>cobra walks<\/jats:italic>\n            for short, are a natural variant of random walks on graphs that can model the spread of disease through contacts or the spread of information in networks. In a\n            <jats:italic>k<\/jats:italic>\n            -cobra walk, at each timestep, a subset of the vertices are active; each active vertex chooses\n            <jats:italic>k<\/jats:italic>\n            random neighbors (sampled independently and uniformly with replacement) that become active at the next step, and these are the only active vertices at the next step. A natural quantity to study for cobra walks is the cover time, which corresponds to the expected time when all nodes have become infected or received the disseminated information.\n          <\/jats:p>\n          <jats:p>\n            In this article, we extend previous results for cobra walks in multiple ways. We show that the cover time for the 2-cobra walk on [0,\n            <jats:italic>n<\/jats:italic>\n            ]\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) (where the order notation hides constant factors that depend on\n            <jats:italic>d<\/jats:italic>\n            ); previous work had shown the cover time was\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u22c5polylog(\n            <jats:italic>n<\/jats:italic>\n            )). We show that the cover time for a 2-cobra walk on an\n            <jats:italic>n<\/jats:italic>\n            -vertex\n            <jats:italic>d<\/jats:italic>\n            -regular graph with conductance \u03c6\n            <jats:sub>G<\/jats:sub>\n            is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            \u03c6\n            <jats:sup>\u22122<\/jats:sup>\n            <jats:sub>G<\/jats:sub>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), significantly generalizing a previous result that held only for expander graphs with sufficiently high expansion. And, finally, we show that the cover time for a 2-cobra walk on a graph with\n            <jats:italic>n<\/jats:italic>\n            vertices and\n            <jats:italic>m<\/jats:italic>\n            edges is always\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            <jats:sup>3\/4<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ; this is the first result showing that the bound of \u0398(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) for the worst-case cover time for random walks can be beaten using 2-cobra walks.\n          <\/jats:p>","DOI":"10.1145\/3209688","type":"journal-article","created":{"date-parts":[[2018,6,15]],"date-time":"2018-06-15T14:14:38Z","timestamp":1529072078000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Better Bounds for Coalescing-Branching Random Walks"],"prefix":"10.1145","volume":"5","author":[{"given":"Michael","family":"Mitzenmacher","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott","family":"Roche","sequence":"additional","affiliation":[{"name":"Akamai Technologies, Cambridge MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780626"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378557"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0377-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.29"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129713"},{"key":"e_1_2_1_6_1","volume-title":"On the trace of branching random walks. arXiv:1002.2781","author":"Benjamini Itai","year":"2010","unstructured":"Itai Benjamini and Sebastian M\u00fcller . 2010. On the trace of branching random walks. arXiv:1002.2781 ( 2010 ). Itai Benjamini and Sebastian M\u00fcller. 2010. On the trace of branching random walks. arXiv:1002.2781 (2010)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873716"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63516"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/100793104"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332440"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933119"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087564"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_57"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2817830"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060106"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060406"},{"key":"e_1_2_1_19_1","volume-title":"Randomized broadcast in networks. Random Structures 8 Algorithms 1, 4","author":"Feige Uriel","year":"1990","unstructured":"Uriel Feige , David Peleg , Prabhakar Raghavan , and Eli Upfal . 1990. Randomized broadcast in networks. Random Structures 8 Algorithms 1, 4 ( 1990 ), 447--460. Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. 1990. Randomized broadcast in networks. Random Structures 8 Algorithms 1, 4 (1990), 447--460."},{"key":"e_1_2_1_20_1","volume-title":"Towsley","author":"Ganesh Ayalvadi J.","year":"2005","unstructured":"Ayalvadi J. Ganesh , Laurent Massouli , and Donald F . Towsley . 2005 . The effect of network topology on the spread of epidemics. In INFOCOM (2006-10-04). IEEE , 1455--1466. http:\/\/dblp.uni-trier.de\/db\/conf\/infocom\/infocom2005.html#GaneshMT05. Ayalvadi J. Ganesh, Laurent Massouli, and Donald F. Towsley. 2005. The effect of network topology on the spread of epidemics. In INFOCOM (2006-10-04). IEEE, 1455--1466. http:\/\/dblp.uni-trier.de\/db\/conf\/infocom\/infocom2005.html#GaneshMT05."},{"volume-title":"The Theory of Branching Processes","author":"Harris Theodore E.","key":"e_1_2_1_21_1","unstructured":"Theodore E. Harris . 1963. The Theory of Branching Processes . Springer-Verlag , Berlin . xiv+230 pages. Theodore E. Harris. 1963. The Theory of Branching Processes. Springer-Verlag, Berlin. xiv+230 pages."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1222441828"},{"volume-title":"Markov Chains and Mixing Times. With a","author":"Levin David Asher","key":"e_1_2_1_23_1","unstructured":"David Asher Levin , Yuval Peres , and Elizabeth Lee Wilmer . 2009. Markov Chains and Mixing Times. With a chapter on coupling from the past by James G. Propp and David B. Wilson. American Mathematical Society , Providence, R.I. Retrieved from http:\/\/opac.inria.fr\/record&equals;b1128575 David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. 2009. Markov Chains and Mixing Times. With a chapter on coupling from the past by James G. Propp and David B. Wilson. American Mathematical Society, Providence, R.I. Retrieved from http:\/\/opac.inria.fr\/record&equals;b1128575"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(92)90038-R"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","key":"e_1_2_1_26_1","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press."},{"key":"e_1_2_1_27_1","unstructured":"Sebastien Roch. 2015. Modern Discrete Probability: An Essential Toolkit. Class Lecture Notes. Retrieved from http:\/\/www.math.wisc.edu\/roch\/mdp\/index.html.  Sebastien Roch. 2015. Modern Discrete Probability: An Essential Toolkit. Class Lecture Notes. Retrieved from http:\/\/www.math.wisc.edu\/roch\/mdp\/index.html."},{"volume-title":"Lecture Notes in Spectral Graph Theory","author":"Spielman Daniel","key":"e_1_2_1_28_1","unstructured":"Daniel Spielman . 2012. Lecture Notes in Spectral Graph Theory . Yale University . Daniel Spielman. 2012. Lecture Notes in Spectral Graph Theory. Yale University."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOP357"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2464831"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-011-0155-y"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209688","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209688","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:33Z","timestamp":1750210773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,31]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3209688"],"URL":"https:\/\/doi.org\/10.1145\/3209688","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2018,3,31]]},"assertion":[{"value":"2017-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}