{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T12:33:49Z","timestamp":1786624429233,"version":"build-2736575974"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T00:00:00Z","timestamp":1786579200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,8,31]]},"abstract":"<jats:p>\n                    Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminating in an almost-complete classification on general graphs and a complete classification on trees. The latter states that, on bounded-degree trees, any LCL problem has deterministic\n                    <jats:italic toggle=\"yes\">worst-case<\/jats:italic>\n                    time complexity\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (1), \u0398 (log\n                    <jats:sup>*<\/jats:sup>\n                    n), \u0398 (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ), or \u0398 (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>\n                      1\/\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    <\/jats:sup>\n                    ) for some positive integer\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    , and all of those complexity classes are nonempty. Moreover, randomness helps only for (some) problems with deterministic worst-case complexity \u0398 (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ), and if randomness helps (asymptotically), then it helps exponentially.\n                  <\/jats:p>\n                  <jats:p>\n                    In this work, we study how many distributed rounds are needed\n                    <jats:italic toggle=\"yes\">on average per node<\/jats:italic>\n                    in order to solve an LCL problem on trees. We obtain a partial classification of the deterministic\n                    <jats:italic toggle=\"yes\">node-averaged<\/jats:italic>\n                    complexity landscape for LCL problems. As our main result, we show that every problem with worst-case round complexity\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) has deterministic node-averaged complexity\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:sup>*<\/jats:sup>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ). Then we show how using randomization we can speed this up and show that every problem with worst case round complexity\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) has randomized node-averaged complexity\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (1). We further establish bounds on the node-averaged complexity of problems with worst-case complexity \u0398 (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>\n                      1\/\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    <\/jats:sup>\n                    ): we show that all these problems have node-averaged complexity\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{\\Omega }(n^{1 \/ (2^k - 1)})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , and that this lower bound is tight for some problems. The lower bound holds even for the randomized case and the upper bound is a deterministic algorithm.\n                  <\/jats:p>\n                  <jats:p\/>","DOI":"10.1145\/3820037","type":"journal-article","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T20:56:51Z","timestamp":1781297811000},"page":"1-67","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Node-Averaged Complexity of Locally Checkable Problems on Trees"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5293-8365","authenticated-orcid":false,"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"Gran Sasso Science Institute","place":["L'Aquila, Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5393-6636","authenticated-orcid":false,"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security","place":["Saarbr\u00fccken, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5343-5953","authenticated-orcid":false,"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Freiburg","place":["Freiburg, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6600-6443","authenticated-orcid":false,"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute","place":["L'Aquila, Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7074-2412","authenticated-orcid":false,"given":"Gustav","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Freiburg","place":["Freiburg, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,13]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00286-1"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.8"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00446-022-00435-9"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331606"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2020.17"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.9"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3662158.3662773"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405715"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00375-2"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2021.8"},{"key":"e_1_3_3_12_2","first-page":"4","volume-title":"Proc. 41st ACM Symp. on Principles of Distributed Computing (PODC)","author":"Balliu Alkida","year":"2022","unstructured":"Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. 2022. Node and edge averaged complexities of local graph problems. In Proc. 41st ACM Symp. on Principles of Distributed Computing (PODC). 4\u201314."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188860"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331605"},{"issue":"1","key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/12088848X","article-title":"Distributed  \\((\\Delta +1)\\) -Coloring in linear (in  \\(\\Delta\\) ) time","volume":"43","author":"Barenboim Leonid","year":"2015","unstructured":"Leonid Barenboim, Michael Elkin, and Fabian Kuhn. 2015. Distributed \\((\\Delta +1)\\) -Coloring in linear (in \\(\\Delta\\) ) time. SIAM J. on Computing 43, 1 (2015), 72\u201395.","journal-title":"SIAM J. on Computing"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3288599.3288601"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087833"},{"issue":"1","key":"e_1_3_3_18_2","first-page":"8:1\u20138:51","article-title":"Distributed edge coloring and a special case of the constructive lov\u00e1sz local lemma","volume":"16","author":"Chang Yi-Jun","year":"2020","unstructured":"Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. 2020. Distributed edge coloring and a special case of the constructive lov\u00e1sz local lemma. ACM Trans. Algorithms 16, 1 (2020), 8:1\u20138:51.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157957"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2023.113710"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2020.18"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405718"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/978-3-319-72050-0_16","volume-title":"Proc. 24th Int. Coll. on Structural Information and Communication Complexity (SIROCCO)","author":"Feuilloley Laurent","year":"2017","unstructured":"Laurent Feuilloley. 2017. How long it takes for an ordinary node with an ordinary ID to output? In Proc. 24th Int. Coll. on Structural Information and Communication Complexity (SIROCCO) 10641 (2017), 263\u2013282."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2017.18"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538452"},{"issue":"5","key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0020-0190(99)00064-2","article-title":"Simple distributed  \\((\\Delta +1)\\) -coloring of graphs","volume":"70","author":"Johansson \u00d6jvind","year":"1999","unstructured":"\u00d6jvind Johansson. 1999. Simple distributed \\((\\Delta +1)\\) -coloring of graphs. Inf. Process. Lett. 70, 5 (1999), 229\u2013232.","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"e_1_3_3_28_2","first-page":"17:1\u201317:44","article-title":"Local computation: Lower and upper bounds","volume":"63","author":"Kuhn Fabian","year":"2016","unstructured":"Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2016. Local computation: Lower and upper bounds. J. ACM 63, 2 (2016), 17:1\u201317:44.","journal-title":"J. ACM"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.43"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3820037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T11:58:49Z","timestamp":1786622329000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3820037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,13]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,8,31]]}},"alternative-id":["10.1145\/3820037"],"URL":"https:\/\/doi.org\/10.1145\/3820037","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,13]]},"assertion":[{"value":"2024-12-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}