{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:39:28Z","timestamp":1782970768891,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":41,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467901","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"283-293","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees"],"prefix":"10.1145","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"University of Freiburg, Freiburg im Breisgau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg im Breisgau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg im Breisgau, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"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\/0196-6774(86)90019-2"},{"key":"e_1_3_2_2_2_1","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989","author":"Awerbuch Baruch","year":"1989","unstructured":"Baruch Awerbuch , Andrew V. Goldberg , Michael Luby , and Serge A. Plotkin . 1989. Network Decomposition and Locality in Distributed Computation . In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989 ). 364--369. https:\/\/doi.org\/10.1109\/SFCS. 1989 .63504 Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. 1989. Network Decomposition and Locality in Distributed Computation. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989). 364--369. https:\/\/doi.org\/10.1109\/SFCS.1989.63504"},{"key":"e_1_3_2_2_3_1","volume-title":"Classification of Distributed Binary Labeling Problems. In 34th International Symposium on Distributed Computing DISC. 17:1-- 17:17","author":"Balliu Alkida","year":"2020","unstructured":"Alkida Balliu , Sebastian Brandt , Yuval Efron , Juho Hirvonen , Yannic Maus , Dennis Olivetti , and Jukka Suomela . 2020 . Classification of Distributed Binary Labeling Problems. In 34th International Symposium on Distributed Computing DISC. 17:1-- 17:17 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.17 Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. 2020. Classification of Distributed Binary Labeling Problems. In 34th International Symposium on Distributed Computing DISC. 17:1-- 17:17. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.17"},{"key":"e_1_3_2_2_4_1","volume-title":"Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Balliu Alkida","year":"2019","unstructured":"Alkida Balliu , Sebastian Brandt , Juho Hirvonen , Dennis Olivetti , Mika\u00ebl Rabie , and Jukka Suomela . 2019 . Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , Baltimore, Maryland, USA, November 9--12 , 2019. 481--497. https:\/\/doi.org\/10.1109\/FOCS.2019.00037 Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika\u00ebl Rabie, and Jukka Suomela. 2019. Lower Bounds for Maximal Matchings and Maximal Independent Sets. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9--12, 2019. 481--497. https:\/\/doi.org\/10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_2_5_1","volume-title":"Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. arXiv","author":"Balliu Alkida","year":"2021","unstructured":"Alkida Balliu , Sebastian Brandt , Fabian Kuhn , and Dennis Olivetti . 2021. Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. arXiv ( 2021 ). Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. 2021. Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. arXiv (2021)."},{"key":"e_1_3_2_2_6_1","volume-title":"Distributed Lower Bounds for Ruling Sets. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS. 365--376","author":"Balliu Alkida","year":"2020","unstructured":"Alkida Balliu , Sebastian Brandt , and Dennis Olivetti . 2020 . Distributed Lower Bounds for Ruling Sets. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS. 365--376 . https:\/\/doi.org\/10.1109\/FOCS46700.2020.00042 arXiv:2004.08282 Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. 2020. Distributed Lower Bounds for Ruling Sets. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS. 365--376. https:\/\/doi.org\/10.1109\/FOCS46700.2020.00042 arXiv:2004.08282"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331605"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_3_2_2_10_1","volume-title":"Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC). 436--446","author":"Barenboim Leonid","year":"2018","unstructured":"Leonid Barenboim , Michael Elkin , and Uri Goldenberg . 2018 . Locally-Iterative Distributed (? + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models . In Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC). 436--446 . Leonid Barenboim, Michael Elkin, and Uri Goldenberg. 2018. Locally-Iterative Distributed (? + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. In Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC). 436--446."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331611"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_2_16_1","volume-title":"69--78. https:\/\/doi.org\/10.1145\/3382734. 3405745","author":"Brandt Sebastian","year":"2020","unstructured":"Sebastian Brandt and Dennis Olivetti . 2020. Truly Tight-in-? Bounds for Bipartite Maximal Matching and Variants. ( 2020 ), 69--78. https:\/\/doi.org\/10.1145\/3382734. 3405745 Sebastian Brandt and Dennis Olivetti. 2020. Truly Tight-in-? Bounds for Bipartite Maximal Matching and Variants. (2020), 69--78. https:\/\/doi.org\/10.1145\/3382734. 3405745"},{"key":"e_1_3_2_2_17_1","volume-title":"Proc. 31st Symp. on Distributed Computing (DISC). 11:1--11:16","author":"Censor-Hillel K.","unstructured":"K. Censor-Hillel , M. Parter , and G. Schwartzman . 2017. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions . In Proc. 31st Symp. on Distributed Computing (DISC). 11:1--11:16 . K. Censor-Hillel, M. Parter, and G. Schwartzman. 2017. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In Proc. 31st Symp. on Distributed Computing (DISC). 11:1--11:16."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"e_1_3_2_2_20_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer . 2017 . Improved Deterministic Distributed Matching via Rounding . In Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017 ). 17:1--17:15. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.17 Manuela Fischer. 2017. Improved Deterministic Distributed Matching via Rounding. In Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017). 17:1--17:15. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.17"},{"key":"e_1_3_2_2_21_1","first-page":"1","article-title":"The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming, ICALP (LIPIcs, Vol. 168)","volume":"128","author":"Fraigniaud Pierre","year":"2020","unstructured":"Pierre Fraigniaud and Ami Paz . 2020 . The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming, ICALP (LIPIcs, Vol. 168) . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 128 : 1 -- 128 :18. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.128 Pierre Fraigniaud and Ami Paz. 2020. The Topology of Local Computing in Networks. In 47th International Colloquium on Automata, Languages, and Programming, ICALP (LIPIcs, Vol. 168). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 128:1--128:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.128","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281111"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.50"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_2_27_1","volume-title":"Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari and Julian Portmann . 2019 . Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond . In Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019 ). 18:1--18:16. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2019.18 Mohsen Ghaffari and Julian Portmann. 2019. Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019). 18:1--18:16. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2019.18"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4226"},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. 23rd Int. Symp. on Distributed Computing (DISC). 221--238","author":"Koufogiannakis Christos","unstructured":"Christos Koufogiannakis and Neal E. Young . 2009. Distributed fractional packing and maximum weighted b-matching via tail-recursive duality . In Proc. 23rd Int. Symp. on Distributed Computing (DISC). 221--238 . Christos Koufogiannakis and Neal E. Young. 2009. Distributed fractional packing and maximum weighted b-matching via tail-recursive duality. In Proc. 23rd Int. Symp. on Distributed Computing (DISC). 221--238."},{"key":"e_1_3_2_2_30_1","volume-title":"Proc. of 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA).","author":"Kuhn Fabian","year":"2009","unstructured":"Fabian Kuhn . 2009 . Local Weak Coloring Algorithms and Implications on Deterministic Symmetry Breaking . In Proc. of 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA). Fabian Kuhn. 2009. Local Weak Coloring Algorithms and Implications on Deterministic Symmetry Breaking. In Proc. of 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_2_31_1","volume-title":"25th International Colloquium, SIROCCO 2018","author":"Kuhn Fabian","year":"2018","unstructured":"Fabian Kuhn , Yannic Maus , and Simon Weidner . 2018 . Deterministic Distributed Ruling Sets of Line Graphs. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018 , Ma'ale HaHamisha, Israel, June 18--21 , 2018, Revised Selected Papers. 193--208. https:\/\/doi.org\/10.1007\/978--3- 030-01325--7_19 Fabian Kuhn, Yannic Maus, and Simon Weidner. 2018. Deterministic Distributed Ruling Sets of Line Graphs. In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18--21, 2018, Revised Selected Papers. 193--208. https:\/\/doi.org\/10.1007\/978--3- 030-01325--7_19"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993813"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Dennis Olivetti. 2019. Round Eliminator: a tool for automatic speedup simulation. https:\/\/github.com\/olidennis\/round-eliminator  Dennis Olivetti. 2019. Round Eliminator: a tool for automatic speedup simulation. https:\/\/github.com\/olidennis\/round-eliminator","DOI":"10.1145\/3382734.3405694"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0097-1"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","location":"Virtual Event Italy","acronym":"PODC '21","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3467901","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467901","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.3467901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":41,"alternative-id":["10.1145\/3465084.3467901","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467901","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"}}]}}