{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:42Z","timestamp":1750220382618,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 2428"],"award-info":[{"award-number":["GRK 2428"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["787367"],"award-info":[{"award-number":["787367"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467912","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"45-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Lower Bounds on the State Complexity of Population Protocols"],"prefix":"10.1145","author":[{"given":"Philipp","family":"Czerner","sequence":"first","affiliation":[{"name":"Technical University of Munich, M\u00fcnchen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javier","family":"Esparza","sequence":"additional","affiliation":[{"name":"Technical University of Munich, M\u00fcnchen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.012"},{"key":"e_1_3_2_2_2_1","volume-title":"Proc. 28^textth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2560--2579","author":"Alistarh Dan","year":"1974","unstructured":"Dan Alistarh , James Aspnes , David Eisenstat , Rati Gelashvili , and Ronald L. Rivest . 2017. Time-Space Trade-offs in Population Protocols . In Proc. 28^textth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2560--2579 . https:\/\/doi.org\/10.1137\/1.978161 1974 782.169 10.1137\/1.9781611974782.169 Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. 2017. Time-Space Trade-offs in Population Protocols. In Proc. 28^textth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2560--2579. https:\/\/doi.org\/10.1137\/1.9781611974782.169"},{"volume-title":"Space-Optimal Majority in Population Protocols","author":"Alistarh Dan","key":"e_1_3_2_2_3_1","unstructured":"Dan Alistarh , James Aspnes , and Rati Gelashvili . 2018. Space-Optimal Majority in Population Protocols . In SODA. SIAM , 2221--2239. Dan Alistarh, James Aspnes, and Rati Gelashvili. 2018. Space-Optimal Majority in Population Protocols. In SODA. SIAM, 2221--2239."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289137.3289150"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Dana Angluin James Aspnes Zo\u00eb Diamadi Michael J. Fischer and Ren\u00e9 Peralta. 2004. Computation in networks of passively mobile finite-state sensors. In PODC. ACM 290--299.  Dana Angluin James Aspnes Zo\u00eb Diamadi Michael J. Fischer and Ren\u00e9 Peralta. 2004. Computation in networks of passively mobile finite-state sensors. In PODC. ACM 290--299.","DOI":"10.1145\/1011767.1011810"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0067-z"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0040-2"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"crossref","unstructured":"A. R. Balasubramanian. 2020. Complexity of controlled bad sequences over finite sets of Nd. In LICS. ACM 130--140.  A. R. Balasubramanian. 2020. Complexity of controlled bad sequences over finite sets of Nd. In LICS. ACM 130--140.","DOI":"10.1145\/3373718.3394753"},{"key":"e_1_3_2_2_11_1","volume-title":"Raskin","author":"Balasubramanian A. R.","year":"2020","unstructured":"A. R. Balasubramanian , Javier Esparza , and Mikhail A . Raskin . 2020 . Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy. CoRR, Vol. abs\/ 2010 .09471 (2020). To appear in Proceedings of FOSSACS 2021. A. R. Balasubramanian, Javier Esparza, and Mikhail A. Raskin. 2020. Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy. CoRR, Vol. abs\/2010.09471 (2020). To appear in Proceedings of FOSSACS 2021."},{"key":"e_1_3_2_2_12_1","volume-title":"STACS (LIPIcs","volume":"15","author":"Blondin Michael","year":"2020","unstructured":"Michael Blondin , Javier Esparza , Blaise Genest , Martin Helfrich , and Stefan Jaax . 2020 . Succinct Population Protocols for Presburger Arithmetic . In STACS (LIPIcs , Vol. 154). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 40:1--40: 15 . Michael Blondin, Javier Esparza, Blaise Genest, Martin Helfrich, and Stefan Jaax. 2020. Succinct Population Protocols for Presburger Arithmetic. In STACS (LIPIcs, Vol. 154). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 40:1--40:15."},{"key":"e_1_3_2_2_13_1","first-page":"1","article-title":"Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In STACS (LIPIcs, Vol. 96)","volume":"16","author":"Blondin Michael","year":"2018","unstructured":"Michael Blondin , Javier Esparza , and Stefan Jaax . 2018 . Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In STACS (LIPIcs, Vol. 96) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 16 : 1 -- 16 :14. Michael Blondin, Javier Esparza, and Stefan Jaax. 2018. Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In STACS (LIPIcs, Vol. 96). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 16:1--16:14.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Philipp Czerner and Javier Esparza. 2021. Lower Bounds on the State Complexity of Population Protocols. arxiv: 2102.11619 [cs.DC]  Philipp Czerner and Javier Esparza. 2021. Lower Bounds on the State Complexity of Population Protocols. arxiv: 2102.11619 [cs.DC]","DOI":"10.1145\/3465084.3467912"},{"key":"e_1_3_2_2_15_1","volume-title":"J\u00e9 r\u00f4 me Leroux, and Filip Mazowiecki","author":"Czerwinski Wojciech","year":"2019","unstructured":"Wojciech Czerwinski , Slawomir Lasota , Ranko Lazic , J\u00e9 r\u00f4 me Leroux, and Filip Mazowiecki . 2019 . The reachability problem for Petri nets is not elementary. In STOC. ACM , 24--33. Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, J\u00e9 r\u00f4 me Leroux, and Filip Mazowiecki. 2019. The reachability problem for Petri nets is not elementary. In STOC. ACM, 24--33."},{"key":"e_1_3_2_2_16_1","volume-title":"Bull. EATCS","volume":"126","author":"Els\u00e4sser Robert","year":"2018","unstructured":"Robert Els\u00e4sser and Tomasz Radzik . 2018 . Recent Results in Population Protocols for Exact Majority and Leader Election . Bull. EATCS , Vol. 126 (2018). Robert Els\u00e4sser and Tomasz Radzik. 2018. Recent Results in Population Protocols for Exact Majority and Leader Election. Bull. EATCS, Vol. 126 (2018)."},{"key":"e_1_3_2_2_17_1","unstructured":"Javier Esparza. 2019. Petri Nets Lecture Notes. https:\/\/archive.model.in.tum.de\/um\/courses\/petri\/SS2019\/PNSkript.pdf  Javier Esparza. 2019. Petri Nets Lecture Notes. https:\/\/archive.model.in.tum.de\/um\/courses\/petri\/SS2019\/PNSkript.pdf"},{"volume-title":"Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma","author":"Figueira Diego","key":"e_1_3_2_2_18_1","unstructured":"Diego Figueira , Santiago Figueira , Sylvain Schmitz , and Philippe Schnoebelen . 2011. Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma . In LICS. IEEE Computer Society , 269--278. Diego Figueira, Santiago Figueira, Sylvain Schmitz, and Philippe Schnoebelen. 2011. Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma. In LICS. IEEE Computer Society, 269--278."},{"key":"e_1_3_2_2_19_1","article-title":"Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election","volume":"68","author":"Gkasieniec Leszek","year":"2020","unstructured":"Leszek Gkasieniec and Grzegorz Stachowiak . 2020 . Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election . J. ACM , Vol. 68 , 1 (2020). Leszek Gkasieniec and Grzegorz Stachowiak. 2020. Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election. J. ACM, Vol. 68, 1 (2020).","journal-title":"J. ACM"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3242953.3242964"},{"key":"e_1_3_2_2_21_1","volume-title":"CONCUR (LIPIcs","volume":"16","author":"Horn Florian","year":"2020","unstructured":"Florian Horn and Arnaud Sangnier . 2020 . Deciding the Existence of Cut-Off in Parameterized Rendez-Vous Networks . In CONCUR (LIPIcs , Vol. 171). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 46:1--46: 16 . Florian Horn and Arnaud Sangnier. 2020. Deciding the Existence of Cut-Off in Parameterized Rendez-Vous Networks. In CONCUR (LIPIcs, Vol. 171). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 46:1--46:16."},{"volume-title":"Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension","author":"Leroux J\u00e9r\u00f4me","key":"e_1_3_2_2_22_1","unstructured":"J\u00e9r\u00f4me Leroux and Sylvain Schmitz . 2019. Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension . In LICS. IEEE , 1--13. J\u00e9r\u00f4me Leroux and Sylvain Schmitz. 2019. Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension. In LICS. IEEE, 1--13."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90029-X"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.24143"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90036-1"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858784"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1978-0500555-0"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467912","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467912","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467912"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":27,"alternative-id":["10.1145\/3465084.3467912","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467912","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}