{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:21Z","timestamp":1750693461346,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"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":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538419","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"4-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Node and Edge Averaged Complexities of Local Graph Problems"],"prefix":"10.1145","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"Gran Sasso Science Institute, L'Aquila, Italy"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, L'Aquila, Italy"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Ahmadi Mohamad","year":"2018","unstructured":"Mohamad Ahmadi , Fabian Kuhn , and Rotem Oshman . 2018 . Distributed approximate maximum matching in the CONGEST model . In Proceedings of the International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. 2018. Distributed approximate maximum matching in the CONGEST model. In Proceedings of the International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10003"},{"volume-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS). 364--369","author":"Awerbuch B.","key":"e_1_3_2_2_4_1","unstructured":"B. Awerbuch , A. V. Goldberg , M. Luby , and S. A. Plotkin . 1989. Network Decomposition and Locality in Distributed Computation . In Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS). 364--369 . B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. 1989. Network Decomposition and Locality in Distributed Computation. In Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS). 364--369."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520027"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087806"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767410"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_2_10_1","volume-title":"Proc. 35th Int. Symp. on Distributed Computing (DISC) (LIPIcs","volume":"19","author":"Barenboim Leonid","year":"2021","unstructured":"Leonid Barenboim and Tzalik Maimon . 2021 . Deterministic Logarithmic Completeness in the Distributed Sleeping Model . In Proc. 35th Int. Symp. on Distributed Computing (DISC) (LIPIcs , Vol. 209). 10:1--10: 19 . Leonid Barenboim and Tzalik Maimon. 2021. Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In Proc. 35th Int. Symp. on Distributed Computing (DISC) (LIPIcs, Vol. 209). 10:1--10:19."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3288599.3288601"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1158604"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405713"},{"volume-title":"Proc. 57th IEEE Symp. on Foundations of Computer Science (FOCS).","author":"Chang Y.-J.","key":"e_1_3_2_2_15_1","unstructured":"Y.-J. Chang , T. Kopelowitz , and S. Pettie . 2016. An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model . In Proc. 57th IEEE Symp. on Foundations of Computer Science (FOCS). Y.-J. Chang, T. Kopelowitz, and S. Pettie. 2016. An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. In Proc. 57th IEEE Symp. on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341111"},{"volume-title":"Proc. 50th ACM Symp. on Theory of Computing (STOC).","author":"Chang Y.-J.","key":"e_1_3_2_2_17_1","unstructured":"Y.-J. Chang , W. Li , and S. Pettie . 2018. An Optimal Distributed Coloring Algorithm? . In Proc. 50th ACM Symp. on Theory of Computing (STOC). Y.-J. Chang, W. Li, and S. Pettie. 2018. An Optimal Distributed Coloring Algorithm?. In Proc. 50th ACM Symp. on Theory of Computing (STOC)."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405718"},{"key":"e_1_3_2_2_19_1","volume-title":"4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11--12","author":"Coupette Corinna","year":"2021","unstructured":"Corinna Coupette and Christoph Lenzen . 2021 . A Breezing Proof of the KMW Bound . In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11--12 , 2021. SIAM, 184--195. Corinna Coupette and Christoph Lenzen. 2021. A Breezing Proof of the KMW Bound. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11--12, 2021. SIAM, 184--195."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.01.023"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0344-4"},{"key":"e_1_3_2_2_22_1","unstructured":"M. Fischer and M. Ghaffari. 2017. Sublogarithmic distributed algorithms for Lovasz local lemma and the complexity hierarchy. arXiv preprint arXiv:1705.04840 (2017).  M. Fischer and M. Ghaffari. 2017. Sublogarithmic distributed algorithms for Lovasz local lemma and the complexity hierarchy. arXiv preprint arXiv:1705.04840 (2017)."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS). 662--673","author":"Ghaffari M.","key":"e_1_3_2_2_24_1","unstructured":"M. Ghaffari , D. Harris , and F. Kuhn . 2018. On derandomizing local distributed algorithms . In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 662--673 . M. Ghaffari, D. Harris, and F. Kuhn. 2018. On derandomizing local distributed algorithms. In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 662--673."},{"key":"e_1_3_2_2_25_1","volume-title":"Proc. 62nd IEEE Symp. on Foundations of Computer Science (FOCS).","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2021 . Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition . In Proc. 62nd IEEE Symp. on Foundations of Computer Science (FOCS). Mohsen Ghaffari and Fabian Kuhn. 2021. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. In Proc. 62nd IEEE Symp. on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039852"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.166"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897533"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00064-2"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571833"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45655-4_31"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.49"},{"volume-title":"Proc. 23rd ACM Symp. on Principles of Distributed Computing (PODC). 300--309","author":"Kuhn F.","key":"e_1_3_2_2_34_1","unstructured":"F. Kuhn , T. Moscibroda , and R. Wattenhofer . 2004. What Cannot Be Computed Locally! . In Proc. 23rd ACM Symp. on Principles of Distributed Computing (PODC). 300--309 . F. Kuhn, T. Moscibroda, and R. Wattenhofer. 2004. What Cannot Be Computed Locally!. In Proc. 23rd ACM Symp. on Principles of Distributed Computing (PODC). 300--309."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90033-S"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.877942"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"crossref","unstructured":"D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.  D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"volume-title":"Proc. 52nd ACM Symp. on Theory of Computing (STOC). 350--363","author":"Rozhon V.","key":"e_1_3_2_2_42_1","unstructured":"V. Rozhon and M. Ghaffari . 2020. Polylogarithmic-time deterministic network decomposition and distributed derandomization . In Proc. 52nd ACM Symp. on Theory of Computing (STOC). 350--363 . V. Rozhon and M. Ghaffari. 2020. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proc. 52nd ACM Symp. on Theory of Computing (STOC). 350--363."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2846458.2846519"}],"event":{"name":"PODC '22: 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":"Salerno Italy","acronym":"PODC '22"},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538419","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":43,"alternative-id":["10.1145\/3519270.3538419","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538419","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}