{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:12:15Z","timestamp":1762809135201,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":25,"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.3467934","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"263-272","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Locally Checkable Problems in Rooted Trees"],"prefix":"10.1145","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}]},{"given":"Jan","family":"Studen\u00fd","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland"}]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland"}]},{"given":"Aleksandr","family":"Tereshchenko","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331606"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Alkida Balliu Sebastian Brandt Yi-Jun Chang Dennis Olivetti Jan Studen\u00fd Jukka Suomela and Aleksandr Tereshchenko. 2021. Locally Checkable Problems in Rooted Trees. arXiv:2102.09277  Alkida Balliu Sebastian Brandt Yi-Jun Chang Dennis Olivetti Jan Studen\u00fd Jukka Suomela and Aleksandr Tereshchenko. 2021. Locally Checkable Problems in Rooted Trees. arXiv:2102.09277","DOI":"10.1145\/3465084.3467934"},{"key":"e_1_3_2_2_3_1","volume-title":"Proc. 34th International Symposium on Distributed Computing (DISC 2020)","volume":"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 Proc. 34th International Symposium on Distributed Computing (DISC 2020) (LIPIcs, Vol. 179). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 17:1--17: 17 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.17 arXiv:1911.13294 Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. 2020. Classification of distributed binary labeling problems. In Proc. 34th International Symposium on Distributed Computing (DISC 2020) (LIPIcs, Vol. 179). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 17:1--17:17. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.17 arXiv:1911.13294"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_2_5_1","unstructured":"Alkida Balliu Sebastian Brandt Dennis Olivetti and Jukka Suomela. 2020. Almost global problems in the LOCAL model. Distributed Computing. https:\/\/doi.org\/10. 1007\/s00446-020-00375-2 arXiv:1805.04776  Alkida Balliu Sebastian Brandt Dennis Olivetti and Jukka Suomela. 2020. Almost global problems in the LOCAL model. Distributed Computing. https:\/\/doi.org\/10. 1007\/s00446-020-00375-2 arXiv:1805.04776"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405715"},{"key":"e_1_3_2_2_7_1","unstructured":"Alkida Balliu Keren Censor-Hillel Yannic Maus Dennis Olivetti and Jukka Suomela. 2021. Locally Checkable Labelings with Small Messages. arXiv:2105.05574  Alkida Balliu Keren Censor-Hillel Yannic Maus Dennis Olivetti and Jukka Suomela. 2021. Locally Checkable Labelings with Small Messages. arXiv:2105.05574"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188860"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331605"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331611"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087833"},{"key":"e_1_3_2_2_13_1","volume-title":"Proc. 34th International Symposium on Distributed Computing (DISC 2020)","volume":"17","author":"Chang Yi-Jun","year":"2020","unstructured":"Yi-Jun Chang . 2020 . The Complexity Landscape of Distributed Locally Checkable Problems on Trees . In Proc. 34th International Symposium on Distributed Computing (DISC 2020) (LIPIcs, Vol. 179). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 18:1--18: 17 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.18 Yi-Jun Chang. 2020. The Complexity Landscape of Distributed Locally Checkable Problems on Trees. In Proc. 34th International Symposium on Distributed Computing (DISC 2020) (LIPIcs, Vol. 179). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 18:1--18:17. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.18"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157957"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79527-6_3"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_3_2_2_19_1","volume-title":"Proc. 31st International Symposium on Distributed Computing (DISC 2017)","volume":"16","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer and Mohsen Ghaffari . 2017 . Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local Lemma, and the Complexity Hierarchy . In Proc. 31st International Symposium on Distributed Computing (DISC 2017) (LIPIcs, Vol. 91). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 18:1--18: 16 . https: \/\/doi.org\/10.4230\/LIPIcs.DISC.2017.18 Manuela Fischer and Mohsen Ghaffari. 2017. Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local Lemma, and the Complexity Hierarchy. In Proc. 31st International Symposium on Distributed Computing (DISC 2017) (LIPIcs, Vol. 91). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 18:1--18:16. https: \/\/doi.org\/10.4230\/LIPIcs.DISC.2017.18"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Dennis Olivetti. 2020. Round Eliminator: a tool for automatic speedup simulation. https:\/\/github.com\/olidennis\/round-eliminator  Dennis Olivetti. 2020. 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_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_2_25_1","unstructured":"Jan Studen\u00fd and Aleksandr Tereshchenko. 2021. Rooted Tree Classifier. https: \/\/github.com\/jendas1\/rooted-tree-classifier  Jan Studen\u00fd and Aleksandr Tereshchenko. 2021. Rooted Tree Classifier. https: \/\/github.com\/jendas1\/rooted-tree-classifier"}],"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.3467934","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467934","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.3467934"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":25,"alternative-id":["10.1145\/3465084.3467934","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467934","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"}}]}}