{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T17:00:05Z","timestamp":1784307605019,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1514383 CCF-1637546 and CCF-1815316"],"award-info":[{"award-number":["CCF-1514383 CCF-1637546 and CCF-1815316"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331607","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:21Z","timestamp":1563542241000},"page":"471-480","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["The Complexity of (\u0394+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation"],"prefix":"10.1145","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manuela","family":"Fischer","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[{"name":"ETH Zurich & University of Freiburg, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yufan","family":"Zheng","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755586"},{"key":"e_1_3_2_1_2_1","unstructured":"Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method 4th ed.). Wiley Publishing.   Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method 4th ed.). Wiley Publishing."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_5_1","unstructured":"Sepehr Assadi. 2017. Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599 (2017).  Sepehr Assadi. 2017. Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599 (2017)."},{"key":"e_1_3_2_1_6_1","volume-title":"Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Assadi Sepehr","year":"2019"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310483"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi Xiaorui Sun and Omri Weinstein. 2018. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. arXiv preprint arXiv:1805.02974 (2018).  Sepehr Assadi Xiaorui Sun and Omri Weinstein. 2018. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. arXiv preprint arXiv:1805.02974 (2018).","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212769"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_11_1","volume-title":"CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings. 41--52","author":"Barenboim Leonid","year":"2018"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_3_2_1_14_1","volume-title":"31st International Symposium on Distributed Computing (DISC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)),, Andr\u00e9a W","author":"Becker Ruben"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_39"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175346"},{"key":"e_1_3_2_1_17_1","unstructured":"Sebastian Brandt Manuela Fischer and Jara Uitto. 2018. Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with n \u03b5 Memory per Machine. arXiv preprint arXiv:1802.06748 (2018).  Sebastian Brandt Manuela Fischer and Jara Uitto. 2018. Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with n \u03b5 Memory per Machine. arXiv preprint arXiv:1802.06748 (2018)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Keren Censor-Hillel Petteri Kaski Janne H. Korhonen Christoph Lenzen Ami Paz and Jukka Suomela. 2016. Algebraic methods in the congested clique. Distributed Computing (2016).  Keren Censor-Hillel Petteri Kaski Janne H. Korhonen Christoph Lenzen Ami Paz and Jukka Suomela. 2016. Algebraic methods in the congested clique. Distributed Computing (2016).","DOI":"10.1145\/2767386.2767414"},{"key":"e_1_3_2_1_19_1","unstructured":"Keren Censor-Hillel Dean Leitersdorf and Elia Turner. 2018 Sparse Matrix Multiplication with Bandwidth Restricted All-to-All Communication. CoR Vol. abs\/1802.04789 (2018).  Keren Censor-Hillel Dean Leitersdorf and Elia Turner. 2018 Sparse Matrix Multiplication with Bandwidth Restricted All-to-All Communication. CoR Vol. abs\/1802.04789 (2018)."},{"key":"e_1_3_2_1_20_1","unstructured":"Yi-Jun Chang Manuela Fischer Mohsen Ghaffari Jara Uitto and Yufan Zheng. 2018a. The Complexity of (\u0394 1) Coloring in Congested Clique Massively Parallel Computation and Centralized Local Computation. CoRR Vol. abs\/1808.08419 (2018). arxiv: 1808.08419 http:\/\/arxiv.org\/abs\/1808.08419  Yi-Jun Chang Manuela Fischer Mohsen Ghaffari Jara Uitto and Yufan Zheng. 2018a. The Complexity of (\u0394 1) Coloring in Congested Clique Massively Parallel Computation and Centralized Local Computation. CoRR Vol. abs\/1808.08419 (2018). arxiv: 1808.08419 http:\/\/arxiv.org\/abs\/1808.08419"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI). USENIX Association","author":"Dean Jeffrey","year":"2004"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings 31st International Symposium on Distributed Computing (DISC). 18:1--18:16","author":"Fischer Manuela","year":"2017"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.73"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Francois Le Gall. 2016. Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. In DISC.  Francois Le Gall. 2016. Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. In DISC.","DOI":"10.1007\/978-3-662-53426-7_5"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087830"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310534"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210386"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.029"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.029"},{"key":"e_1_3_2_1_39_1","volume-title":"Distributed Computing","author":"Hegeman James W"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272998.1273005"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175472"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835772"},{"key":"e_1_3_2_1_47_1","volume-title":"Bulletin of EATCS","volume":"2","author":"Levi Reut","year":"2017"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"}],"event":{"name":"PODC '19: ACM Symposium on Principles of Distributed Computing","location":"Toronto ON Canada","acronym":"PODC '19","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331607","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:02Z","timestamp":1750208522000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":49,"alternative-id":["10.1145\/3293611.3331607","10.1145\/3293611"],"URL":"https:\/\/doi.org\/10.1145\/3293611.3331607","relation":{},"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}