{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:06:25Z","timestamp":1749873985609,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733501","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"349-359","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Density-Dependent Graph Orientation and Coloring in Scalable MPC"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4213-9898","authenticated-orcid":false,"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[{"name":"MIT, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1057-9429","authenticated-orcid":false,"given":"Christoph","family":"Grunau","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"[n.d.]. Massively Parallel Algorithms. https:\/\/people.csail.mit.edu\/ghaffari\/MPA19\/Notes\/MPA.pdf."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310483"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch99"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400757"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00095"},{"key":"e_1_3_2_1_11_1","volume-title":"ACM Symp. on Principles of Distributed Computing (PODC). 471\u2013480","author":"Chang Y.-J.","unstructured":"Y.-J. Chang, M. Fischer, M. Ghaffari, J. Uitto, and Y. Zheng. 2019. The Complexity of (\u0394 + 1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation. In ACM Symp. on Principles of Distributed Computing (PODC). 471\u2013480."},{"key":"e_1_3_2_1_12_1","volume-title":"ACM Symp. on Theory of Computing (STOC).","author":"Chang Yi-Jun","year":"2018","unstructured":"Yi-Jun Chang, Wenzheng Li, and Seth Pettie. 2018. An Optimal Distributed (\u0394 + 1)-Coloring Algorithm?. In ACM Symp. on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585111"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520055"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3451992"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467937"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_18_1","volume-title":"Improved Deterministic Connectivity in Massively Parallel Computation. In 36th International Symposium on Distributed Computing.","author":"Fischer Manuela","year":"2022","unstructured":"Manuela Fischer, Jeff Giliberti, and Christoph Grunau. 2022. Improved Deterministic Connectivity in Massively Parallel Computation. In 36th International Symposium on Distributed Computing."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591081"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649782"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00007"},{"key":"e_1_3_2_1_22_1","volume-title":"34th International Symposium on Distributed Computing.","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 34th International Symposium on Distributed Computing."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_1_24_1","volume-title":"International Conference on Machine Learning. PMLR, 2201\u20132210","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovi\u0107. 2019. Improved parallel algorithms for density-based network clustering. In International Conference on Machine Learning. PMLR, 2201\u20132210."},{"key":"e_1_3_2_1_25_1","volume-title":"Simple and Near-Optimal Distributed Coloring for Sparse Graphs. In 31st International Symposium on Distributed Computing (DISC","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Christiana Lymouri. 2017. Simple and Near-Optimal Distributed Coloring for Sparse Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.166"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 23","author":"Grunau Christoph","year":"2023","unstructured":"Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto. 2023. Conditionally Optimal Parallel Coloring of Forests. In Proceedings of the International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 23."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520023"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Sungjin Im Ravi Kumar Silvio Lattanzi Benjamin Moseley Sergei Vassilvitskii et al. 2023. Massively parallel computation: Algorithms and applications. Foundations and Trends\u00ae in Optimization 5 4 (2023) 340\u2013417.","DOI":"10.1561\/2400000025"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3662158.3662821"},{"key":"e_1_3_2_1_35_1","volume-title":"Proc. 22nd Symp. on Distributed Computing (DISC). 394\u2013407","author":"Lenzen C.","unstructured":"C. Lenzen and R. Wattenhofer. 2008. Leveraging Linial's Locality Limit. In Proc. 22nd Symp. on Distributed Computing (DISC). 394\u2013407."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_1_41_1","volume-title":"Distributed Dense Subgraph Detection and Low Outdegree Orientation. In 34th International Symposium on Distributed Computing.","author":"Su Hsin-Hao","year":"2020","unstructured":"Hsin-Hao Su and Hoa T Vu. 2020. Distributed Dense Subgraph Detection and Low Outdegree Orientation. In 34th International Symposium on Distributed Computing."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"e_1_3_2_1_43_1","volume-title":"Hadoop: The definitive guide. \"O'Reilly Media","author":"White Tom","year":"2012","unstructured":"Tom White. 2012. Hadoop: The definitive guide. \"O'Reilly Media, Inc.\"."},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing."}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:25:58Z","timestamp":1749824758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":44,"alternative-id":["10.1145\/3732772.3733501","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733501","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}