{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:39:00Z","timestamp":1773931140070,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"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,11]]},"DOI":"10.1145\/3490148.3538566","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"45-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Average Awake Complexity of MIS and Matching"],"prefix":"10.1145","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Julian","family":"Portmann","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_1_3_1","volume-title":"Node and Edge Averaged Complexities of Local Graph Problems. manuscript","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. manuscript ( 2022 ). Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. 2022. Node and Edge Averaged Complexities of Local Graph Problems. manuscript (2022)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087806"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_1_6_1","volume-title":"Distributed Graph Coloring: Fundamentals and Recent Developments","author":"Barenboim Leonid","unstructured":"Leonid Barenboim and Michael Elkin . 2013. Distributed Graph Coloring: Fundamentals and Recent Developments . Morgan & Claypool Publishers . Leonid Barenboim and Michael Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3288599.3288601"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405718"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.01.023"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0344-4"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175445"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310485"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_1_18_1","volume-title":"33rd International Symposium on Distributed Computing (DISC","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 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Mohsen Ghaffari and Julian Portmann. 2019. Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00064-2"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_1_27_1","volume-title":"Symmetry Breaking in the Congest Model: Time-and Message- Efficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing (DISC","author":"Pai Shreyas","year":"2017","unstructured":"Shreyas Pai , Gopal Pandurangan , Sriram V Pemmaraju , Talal Riaz , and Peter Robinson . 2017 . Symmetry Breaking in the Congest Model: Time-and Message- Efficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Shreyas Pai, Gopal Pandurangan, Sriram V Pemmaraju, Talal Riaz, and Peter Robinson. 2017. Symmetry Breaking in the Congest Model: Time-and Message- Efficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_28_1","volume-title":"Some simple distributed algorithms for sparse networks. Distributed computing 14, 2","author":"Panconesi Alessandro","year":"2001","unstructured":"Alessandro Panconesi and Romeo Rizzi . 2001. Some simple distributed algorithms for sparse networks. Distributed computing 14, 2 ( 2001 ), 97--100. Alessandro Panconesi and Romeo Rizzi. 2001. Some simple distributed algorithms for sparse networks. Distributed computing 14, 2 (2001), 97--100."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129769"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_31_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Pemmaraju Sriram V","unstructured":"Sriram V Pemmaraju . 2001. Equitable coloring extends Chernoff-Hoeffding bounds . In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques . Springer , 285--296. Sriram V Pemmaraju. 2001. Equitable coloring extends Chernoff-Hoeffding bounds. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Springer, 285--296."},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC).","author":"Ghaffari Mohsen","year":"2020","unstructured":"Mohsen Ghaffari . 2020 . Polylogarithmic-time deterministic network decomposition and distributed derandomization . In Proceedings of the ACM Symposium on Theory of Computing (STOC). to appear, arXiv:1907.10937. Mohsen Ghaffari. 2020. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the ACM Symposium on Theory of Computing (STOC). to appear, arXiv:1907.10937."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400758"}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Philadelphia PA USA","acronym":"SPAA '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538566","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538566","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:08Z","timestamp":1750191128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538566"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":33,"alternative-id":["10.1145\/3490148.3538566","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538566","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}