{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T17:10:01Z","timestamp":1763226601138,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"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"],"award-info":[{"award-number":["CCF-1514383, CCF-1637546"]}],"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":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188964","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"445-456","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["An optimal distributed (\u0394+1)-coloring algorithm?"],"prefix":"10.1145","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenzheng","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"unstructured":"N. Alon L. Babai and A. Itai. 1986.  N. Alon L. Babai and A. Itai. 1986.","key":"e_1_3_2_2_1_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2_1","DOI":"10.1016\/0196-6774(86)90019-2"},{"unstructured":"B. Awerbuch A. V. Goldberg M. Luby and S. A. Plotkin. 1989.  B. Awerbuch A. V. Goldberg M. Luby and S. A. Plotkin. 1989.","key":"e_1_3_2_2_3_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_4_1","DOI":"10.1109\/SFCS.1989.63504"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_5_1","DOI":"10.1145\/2767386.2767410"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_6_1","DOI":"10.1137\/12088848X"},{"unstructured":"L. Barenboim M. Elkin S. Pettie and J. Schneider. 2016.  L. Barenboim M. Elkin S. Pettie and J. Schneider. 2016.","key":"e_1_3_2_2_7_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_8_1","DOI":"10.1145\/2903137"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_9_1","DOI":"10.1145\/2611462.2611512"},{"unstructured":"Y.-J. Chang W. Li and S. Pettie. 2017. An Optimal Distributed ( \u2206+1)-Coloring Algorithm? CoRR abs\/1711.01361 (2017). arXiv: 1711.01361 http:\/\/arxiv.org\/abs\/ 1711.01361  Y.-J. Chang W. Li and S. Pettie. 2017. An Optimal Distributed ( \u2206+1)-Coloring Algorithm? CoRR abs\/1711.01361 (2017). arXiv: 1711.01361 http:\/\/arxiv.org\/abs\/ 1711.01361","key":"e_1_3_2_2_10_1"},{"volume-title":"Proceedings 57th IEEE Symposium on Foundations of Computer Science (FOCS). 615\u2013 624","author":"Chang Y.-J.","unstructured":"Y.-J. Chang , T. Kopelowitz , and S. Pettie . 2016. An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model . In Proceedings 57th IEEE Symposium on Foundations of Computer Science (FOCS). 615\u2013 624 . Y.-J. Chang, T. Kopelowitz, and S. Pettie. 2016. An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model. In Proceedings 57th IEEE Symposium on Foundations of Computer Science (FOCS). 615\u2013 624.","key":"e_1_3_2_2_11_1"},{"volume-title":"Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Chang Y.-J.","unstructured":"Y.-J. Chang and S. Pettie . 2017. A Time Hierarchy Theorem for the LOCAL Model . In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS). Y.-J. Chang and S. Pettie. 2017. A Time Hierarchy Theorem for the LOCAL Model. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS).","key":"e_1_3_2_2_12_1"},{"unstructured":"D. P. Dubhashi and A. Panconesi. 2009.  D. P. Dubhashi and A. Panconesi. 2009.","key":"e_1_3_2_2_13_1"},{"unstructured":"Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.   Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.","key":"e_1_3_2_2_14_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_15_1","DOI":"10.1002\/(SICI)1098-2418(199809)13:2%3C99::AID-RSA1%3E3.0.CO;2-M"},{"unstructured":"M. Elkin S. Pettie and H.-H. Su. 2015.  M. Elkin S. Pettie and H.-H. Su. 2015.","key":"e_1_3_2_2_16_1"},{"volume-title":"Maximal Matching in the Distributed Setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355\u2013370","author":"Much Edge Coloring","unstructured":"( 2 \u2206 \u2212 1)- Edge Coloring is Much Easier than Maximal Matching in the Distributed Setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355\u2013370 . (2 \u2206 \u2212 1)-Edge Coloring is Much Easier than Maximal Matching in the Distributed Setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355\u2013370.","key":"e_1_3_2_2_17_1"},{"unstructured":"M. Fischer and M. Ghaffari. 2017.  M. Fischer and M. Ghaffari. 2017.","key":"e_1_3_2_2_18_1"},{"volume-title":"Distributed Algorithms for Lov\u00e1sz Local Lemma with Implications on Complexity Hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC). 18:1\u201318:16","author":"Sublogarithmic","unstructured":"Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local Lemma with Implications on Complexity Hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC). 18:1\u201318:16 . Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local Lemma with Implications on Complexity Hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC). 18:1\u201318:16.","key":"e_1_3_2_2_19_1"},{"unstructured":"M. Fischer M. Ghaffari and F. Kuhn. 2017.  M. Fischer M. Ghaffari and F. Kuhn. 2017.","key":"e_1_3_2_2_20_1"},{"volume-title":"Hypergraph Maximal Matching. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Edge Deterministic Distributed","unstructured":"Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS). Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching. In Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS).","key":"e_1_3_2_2_21_1"},{"volume-title":"Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 625\u2013634","author":"Fraigniaud P.","unstructured":"P. Fraigniaud , M. Heinrich , and A. Kosowski . 2016. Local conflict coloring . In Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 625\u2013634 . P. Fraigniaud, M. Heinrich, and A. Kosowski. 2016. Local conflict coloring. In Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 625\u2013634.","key":"e_1_3_2_2_22_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_23_1","DOI":"10.5555\/2884435.2884455"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_24_1","DOI":"10.1145\/28395.28429"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_25_1","DOI":"10.1016\/0020-0190(87)90169-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_26_1","DOI":"10.1145\/2897518.2897533"},{"unstructured":"W. Hoeffding. 1963.  W. Hoeffding. 1963.","key":"e_1_3_2_2_27_1"},{"key":"e_1_3_2_2_28_1","volume-title":"13\u201330","author":"Bounded Random Variables Probability Inequalities","year":"1963","unstructured":"Probability Inequalities for Sums of Bounded Random Variables . J. Amer . Statist. Assoc. 58, 301 ( 1963 ), 13\u201330 . Probability Inequalities for Sums of Bounded Random Variables. J. Amer. Statist. Assoc. 58, 301 (1963), 13\u201330."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_29_1","DOI":"10.1016\/S0020-0190(99)00064-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_30_1","DOI":"10.1145\/2742012"},{"unstructured":"F. Kuhn and R. Wattenhofer. 2006.  F. Kuhn and R. Wattenhofer. 2006.","key":"e_1_3_2_2_31_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_32_1","DOI":"10.1145\/1146381.1146387"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_33_1","DOI":"10.1137\/0221015"},{"unstructured":"M. Luby. 1986.  M. Luby. 1986.","key":"e_1_3_2_2_34_1"},{"key":"e_1_3_2_2_35_1","volume-title":"1036\u20131053","author":"Comput A","year":"1986","unstructured":"A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput . 15, 4 ( 1986 ), 1036\u20131053 . A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 4 (1986), 1036\u20131053."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_36_1","DOI":"10.1137\/0404036"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_37_1","DOI":"10.1006\/jagm.1996.0017"},{"unstructured":"D. Peleg. 2000.  D. Peleg. 2000.","key":"e_1_3_2_2_38_1"},{"unstructured":"Distributed Computing: A Locality-Sensitive Approach. SIAM.  Distributed Computing: A Locality-Sensitive Approach. SIAM.","key":"e_1_3_2_2_39_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '18","name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188964","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188964","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188964","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:07Z","timestamp":1750208887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188964"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":39,"alternative-id":["10.1145\/3188745.3188964","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188964","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}