{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:12:21Z","timestamp":1762809141589,"version":"3.41.0"},"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"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["754411"],"award-info":[{"award-number":["754411"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V01305X\/1"],"award-info":[{"award-number":["EP\/V01305X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["949083"],"award-info":[{"award-number":["949083"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467937","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"469-479","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Improved Deterministic (\u0394+1) Coloring in Low-Space MPC"],"prefix":"10.1145","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}]},{"given":"Peter","family":"Davies","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}]},{"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Weizmann Institute of Science, Rehovot, Israel"}]}],"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\/2591796.2591805"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3404504"},{"key":"e_1_3_2_2_4_1","volume-title":"The Locality of Distributed Symmetry Breaking. 63, 3","author":"Barenboim Leonid","year":"2016","unstructured":"Leonid Barenboim , Michael Elkin , Seth Pettie , and Johannes Schneider . 2016. The Locality of Distributed Symmetry Breaking. 63, 3 ( 2016 ), 20:1--20:45. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2016. The Locality of Distributed Symmetry Breaking. 63, 3 (2016), 20:1--20:45."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00095"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/120875673"},{"key":"e_1_3_2_2_8_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC). 11:1--11:16","author":"Censor-Hillel Keren","year":"2017","unstructured":"Keren Censor-Hillel , Merav Parter , and Gregory Schwartzman . 2017 . Derandomizing Local Distributed Algorithms under Bandwidth Restrictions . In Proceedings of the 31st International Symposium on Distributed Computing (DISC). 11:1--11:16 . Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. 2017. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In Proceedings of the 31st International Symposium on Distributed Computing (DISC). 11:1--11:16."},{"key":"e_1_3_2_2_9_1","volume-title":"An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. 48, 1","author":"Chang Yi-Jun","year":"2019","unstructured":"Yi-Jun Chang , Tsvi Kopelowitz , and Seth Pettie . 2019. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. 48, 1 ( 2019 ), 122--143. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. 2019. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. 48, 1 (2019), 122--143."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_2_12_1","volume-title":"Distributed -Coloring via Ultrafast Graph Shattering. 49, 3","author":"Chang Yi-Jun","year":"2020","unstructured":"Yi-Jun Chang , Wenzheng Li , and Seth Pettie . 2020. Distributed -Coloring via Ultrafast Graph Shattering. 49, 3 ( 2020 ), 497--539. Yi-Jun Chang, Wenzheng Li, and Seth Pettie. 2020. Distributed -Coloring via Ultrafast Graph Shattering. 49, 3 (2020), 497--539."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400282"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405751"},{"key":"e_1_3_2_2_15_1","volume-title":"Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC).","author":"Czumaj Artur","year":"2021","unstructured":"Artur Czumaj , Peter Davies , and Merav Parter . 2021 . Component Stability in LowSpace Massively Parallel Computation . In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC). Artur Czumaj, Peter Davies, and Merav Parter. 2021. Component Stability in LowSpace Massively Parallel Computation. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC)."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Anindya De Omid Etesami Luca Trevisan and Madhur Tulsiani. 2010. Improved Pseudorandom Generators for Depth 2 Circuits. In Proceedings of the 13th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and of the 10th the International Conference on Randomization and Computation (RANDOM). 504--517.  Anindya De Omid Etesami Luca Trevisan and Madhur Tulsiani. 2010. Improved Pseudorandom Generators for Depth 2 Circuits. In Proceedings of the 13th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and of the 10th the International Conference on Randomization and Computation (RANDOM). 504--517.","DOI":"10.1007\/978-3-642-15369-3_38"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_2_18_1","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC)","volume":"179","author":"Ghaffari Mohsen","year":"2020","unstructured":"Mohsen Ghaffari , Christoph Grunau , and Ce Jin . 2020 . Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond . In Proceedings of the 34th International Symposium on Distributed Computing (DISC) , Vol. 179 . 34:1--34:18. Mohsen Ghaffari, Christoph Grunau, and Ce Jin. 2020. Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond. In Proceedings of the 34th International Symposium on Distributed Computing (DISC), Vol. 179. 34:1--34:18."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400260"},{"key":"e_1_3_2_2_20_1","volume-title":"Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. CoRR abs\/2011.04511","author":"Ghaffari Mohsen","year":"2020","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2020. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. CoRR abs\/2011.04511 ( 2020 ). Mohsen Ghaffari and Fabian Kuhn. 2020. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. CoRR abs\/2011.04511 (2020)."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.77"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"volume-title":"Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS). 120--129","author":"Gopalan Parikshit","key":"e_1_3_2_2_25_1","unstructured":"Parikshit Gopalan , Raghu Meka , Omer Reingold , Luca Trevisan , and Salil P. Vadhan . 2012. Better Pseudorandom Generators from Milder Pseudorandom Restrictions . In Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS). 120--129 . Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. 2012. Better Pseudorandom Generators from Milder Pseudorandom Restrictions. In Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS). 120--129."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897533"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"volume-title":"Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 28:1--28:18","author":"Kothapalli Kishore","key":"e_1_3_2_2_28_1","unstructured":"Kishore Kothapalli , Shreyas Pai , and Sriram V. Pemmaraju . 2020. Sample-AndGather: Fast Ruling Set Algorithms in the Low-Memory MPC Model . In Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 28:1--28:18 . Kishore Kothapalli, Shreyas Pai, and Sriram V. Pemmaraju. 2020. Sample-AndGather: Fast Ruling Set Algorithms in the Low-Memory MPC Model. In Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 28:1--28:18."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_3_2_2_30_1","volume-title":"Locality in Distributed Graph Algorithms. 21, 1 (Feb","author":"Linial Nathan","year":"1992","unstructured":"Nathan Linial . 1992. Locality in Distributed Graph Algorithms. 21, 1 (Feb . 1992 ), 193--201. Nathan Linial. 1992. Locality in Distributed Graph Algorithms. 21, 1 (Feb. 1992), 193--201."},{"key":"e_1_3_2_2_31_1","volume-title":"MinimumWeight Spanning Tree Construction in ?? (log log??) Communication Rounds. 35, 1","author":"Lotker Zvi","year":"2005","unstructured":"Zvi Lotker , Boaz Patt-Shamir , Elan Pavlov , and David Peleg . 2005. MinimumWeight Spanning Tree Construction in ?? (log log??) Communication Rounds. 35, 1 ( 2005 ), 120--131. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. 2005. MinimumWeight Spanning Tree Construction in ?? (log log??) Communication Rounds. 35, 1 (2005), 120--131."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777428"},{"key":"e_1_3_2_2_33_1","volume-title":"A Simple Parallel Algorithm for the Maximal Independent Set Problem. 15, 4","author":"Luby Michael","year":"1986","unstructured":"Michael Luby . 1986. A Simple Parallel Algorithm for the Maximal Independent Set Problem. 15, 4 ( 1986 ), 1036--1053. Michael Luby. 1986. A Simple Parallel Algorithm for the Maximal Independent Set Problem. 15, 4 (1986), 1036--1053."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90033-S"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316319"},{"key":"e_1_3_2_2_36_1","volume-title":"Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS). 2--11","author":"Nisan Noam","year":"1988","unstructured":"Noam Nisan and Avi Wigderson . 1988 . Hardness vs. Randomness (Extended Abstract) . In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS). 2--11 . Noam Nisan and Avi Wigderson. 1988. Hardness vs. Randomness (Extended Abstract). In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS). 2--11."},{"key":"e_1_3_2_2_37_1","volume-title":"Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. CoRR abs\/1807.08745","author":"Onak Krzysztof","year":"2018","unstructured":"Krzysztof Onak . 2018. Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. CoRR abs\/1807.08745 ( 2018 ). arXiv:1807.08745 Krzysztof Onak. 2018. Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. CoRR abs\/1807.08745 (2018). arXiv:1807.08745"},{"key":"e_1_3_2_2_38_1","first-page":"1","article-title":"(? + 1) Coloring in the Congested Clique Model. In Proceedings of the 45th Annual International Colloquium on Automata","volume":"160","author":"Parter Merav","year":"2018","unstructured":"Merav Parter . 2018 . (? + 1) Coloring in the Congested Clique Model. In Proceedings of the 45th Annual International Colloquium on Automata , Languages and Programming (ICALP). 160 : 1 -- 160 :14. Merav Parter. 2018. (? + 1) Coloring in the Congested Clique Model. In Proceedings of the 45th Annual International Colloquium on Automata, Languages and Programming (ICALP). 160:1--160:14.","journal-title":"Languages and Programming (ICALP)."},{"key":"e_1_3_2_2_39_1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 39:1--39:18","author":"Parter Merav","year":"2018","unstructured":"Merav Parter and Hsin-Hao Su . 2018 . Randomized (?+1)-Coloring in?? (log? ?) Congested Clique Rounds . In Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 39:1--39:18 . Merav Parter and Hsin-Hao Su. 2018. Randomized (?+1)-Coloring in?? (log? ?) Congested Clique Rounds. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 39:1--39:18."},{"key":"e_1_3_2_2_40_1","volume-title":"Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC). 350--363","author":"Ghaffari Mohsen","year":"2020","unstructured":"Mohsen Ghaffari . 2020 . Polylogarithmic-time Deterministic Network Decomposition and Distributed Derandomization . In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC). 350--363 . Mohsen Ghaffari. 2020. Polylogarithmic-time Deterministic Network Decomposition and Distributed Derandomization. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC). 350--363."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"}],"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.3467937","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467937","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.3467937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":41,"alternative-id":["10.1145\/3465084.3467937","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467937","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"}}]}}