{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T14:47:00Z","timestamp":1781102820596,"version":"3.54.1"},"reference-count":21,"publisher":"National Academy of Sciences","issue":"40","license":[{"start":{"date-parts":[[2018,3,19]],"date-time":"2018-03-19T00:00:00Z","timestamp":1521417600000},"content-version":"vor","delay-in-days":181,"URL":"http:\/\/www.pnas.org\/site\/misc\/userlicense.xhtml"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["BIO-1455983"],"award-info":[{"award-number":["BIO-1455983"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1461559"],"award-info":[{"award-number":["CCF-1461559"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF- 0939370"],"award-info":[{"award-number":["CCF- 0939370"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"DOD | USAF | AFMC | Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-13-1-0042"],"award-info":[{"award-number":["FA9550-13-1-0042"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1122374"],"award-info":[{"award-number":["1122374"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2017,10,3]]},"abstract":"<jats:title>Significance<\/jats:title>\n                  <jats:p>Highly complex distributed algorithms are ubiquitous in nature: from the behavior of social insect colonies and bird flocks, to cellular differentiation in embryonic development, to neural information processing. In our research, we study biological computation theoretically, combining a scientific perspective, which seeks to better understand the systems being studied, with an engineering perspective, which takes inspiration from these systems to improve algorithm design. In this work, we focus on the problem of population density estimation in ant colonies, demonstrating that extremely simple algorithms, similar to those used by ants, solve the problem with strong theoretical guarantees and have a number of interesting computational applications.<\/jats:p>","DOI":"10.1073\/pnas.1706439114","type":"journal-article","created":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T20:40:16Z","timestamp":1505853616000},"page":"10534-10541","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":8,"title":["Ant-inspired density estimation via random walks"],"prefix":"10.1073","volume":"114","author":[{"given":"Cameron","family":"Musco","sequence":"first","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3045-265X","authenticated-orcid":false,"given":"Nancy A.","family":"Lynch","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2017,9,19]]},"reference":[{"key":"e_1_3_3_1_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933106"},{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1093\/beheco\/ari020"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0003-3472(05)80877-2"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8739-7_3"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.anbehav.2005.05.024"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1006\/anbe.1993.1134"},{"key":"e_1_3_3_7_2","first-page":"1","volume-title":"Combinatorics, Paul Erdos Is Eighty","author":"Lov\u00e1sz L","year":"1993","unstructured":"L Lov\u00e1sz, Random walks on graphs: A survey. Combinatorics, Paul Erdos Is Eighty (Janos Bolyai Math Soc, Budapest) Vol 2, 1\u201346 (1993)."},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/978-3-642-02927-1_35","volume-title":"Automata, Languages and Programming","author":"Els\u00e4sser R","year":"2009","unstructured":"R Els\u00e4sser, T Sauerwald, Tight bounds for the cover time of multiple random walks. Automata, Languages and Programming (Springer, New York), pp. 415\u2013426 (2009)."},{"key":"e_1_3_3_9_2","unstructured":"V Kanade F Mallmann-Trenn T Sauerwald On coalescence time in graphs\u2013when is coalescing as fast as meeting? arXiv:161102460. (2016)."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_3_3_11_2","unstructured":"KM Chung H Lam Z Liu M Mitzenmacher Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified. arXiv:12010559. (2012)."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.862883"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/984622.984663"},{"key":"e_1_3_3_14_2","first-page":"1","volume-title":"5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops, 2007","author":"Lima L","year":"2007","unstructured":"L Lima, J Barros, Random Walks on Sensor Networks. 5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops, 2007 (Inst Electr Electron Eng, New York), pp. 1\u20135 (2007)."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.anbehav.2004.06.007"},{"key":"e_1_3_3_16_2","first-page":"84","article-title":"The complexity of an optimal non-blocking commutation scheme without reorganization","volume":"9","author":"Bassalygo L","year":"1973","unstructured":"L Bassalygo, M Pinsker, The complexity of an optimal non-blocking commutation scheme without reorganization. Problemy Peredaci Informacii 9, 84\u201387 (1973).","journal-title":"Problemy Peredaci Informacii"},{"key":"e_1_3_3_17_2","unstructured":"M Kurant CT Butts A Markopoulou Graph size estimation. arXiv:1210.0460. (2012)."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2392622.2392628"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2014.02.003"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","unstructured":"M Gjoka M Kurant CT Butts A Markopoulou A walk in Facebook: Uniform sampling of users in online social networks. arXiv:09060060. (2009).","DOI":"10.1145\/1397735.1397743"}],"updated-by":[{"DOI":"10.1073\/pnas.1902577116","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T00:00:00Z","timestamp":1551657600000}}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.1706439114","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.1706439114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T23:08:40Z","timestamp":1693004920000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.1706439114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,19]]},"references-count":21,"journal-issue":{"issue":"40","published-print":{"date-parts":[[2017,10,3]]}},"alternative-id":["10.1073\/pnas.1706439114"],"URL":"https:\/\/doi.org\/10.1073\/pnas.1706439114","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,19]]},"assertion":[{"value":"2017-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}