{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T08:21:41Z","timestamp":1772785301772,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2016,11,8]],"date-time":"2016-11-08T00:00:00Z","timestamp":1478563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISRAEL SCIENCE FOUNDATION","award":["724\/15"],"award-info":[{"award-number":["724\/15"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,12,20]]},"abstract":"<jats:p>\n            We study the distributed (\u0394 + 1)-vertex-coloring and (2\u0394 \u2212 1)-edge-coloring problems. These problems are among the most important and intensively studied problems in distributed computing. Despite very intensive research in the last 30 years, no deterministic algorithms for these problems with sublinear (in \u0394) time have been known so far. Moreover, for more restricted scenarios and some related problems there are lower bounds of \u03a9(\u0394) [G\u00f6\u00f6s et al. 2014; Hirvonen and Suomela 2012; Kuhn and Wattenhofer 2006; Szegedy and Vishwanathan 1993]. The question of the possibility to devise algorithms that overcome this challenging barrier is one of the most fundamental questions in distributed symmetry breaking [Barenboim and Elkin 2009, 2011; G\u00f6\u00f6s et al. 2014; Hirvonen and Suomela 2012; Kuhn 2009; Panconesi and Rizzi 2001]. In this article, we settle this question for (\u0394 + 1)-vertex-coloring and (2\u0394 \u2212 1)-edge-coloring by devising deterministic algorithms that require\n            <jats:italic>O<\/jats:italic>\n            (\u0394\n            <jats:sup>3\/4<\/jats:sup>\n            log \u0394 + log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time in the static, dynamic, and faulty settings. (The term log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            is unavoidable in view of the lower bound of Linial [1987].) Moreover, for (1 +\n            <jats:italic>o<\/jats:italic>\n            (1))\u0394-vertex-coloring and (2 +\n            <jats:italic>o<\/jats:italic>\n            (1))\u0394-edge-coloring we devise algorithms with \u00d5(\u221a\u0394 + log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) deterministic time. This is roughly a quadratic improvement comparing to the state-of-the-art that requires\n            <jats:italic>O<\/jats:italic>\n            (\u0394 + log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time [Barenboim and Elkin 2009; Kuhn 2009; Panconesi and Rizzi 2001]. Our results are actually more general than that since they apply also to a variant of the list-coloring problem that generalizes ordinary coloring.\n          <\/jats:p>\n          <jats:p>\n            Our results are obtained using a novel technique for coloring partially colored graphs (also known as\n            <jats:italic>fixing<\/jats:italic>\n            ). We partition the uncolored parts into a small number of subgraphs with certain helpful properties. Then we color these subgraphs gradually using a technique that employs\n            <jats:italic>constructions of polynomials<\/jats:italic>\n            in a novel way. Our construction is inspired by the algorithm of Linial [1987] for ordinary\n            <jats:italic>O<\/jats:italic>\n            (\u0394\n            <jats:sup>2<\/jats:sup>\n            )-coloring. However, it is a more sophisticated construction that differs from that of Linial [1987] in several important respects. These new insights in using systems of polynomials allow us to significantly speed up the\n            <jats:italic>O<\/jats:italic>\n            (\u0394)-coloring algorithms. Moreover, they allow us to devise algorithms with the same running time also in the more complicated settings of dynamic and faulty networks.\n          <\/jats:p>","DOI":"10.1145\/2979675","type":"journal-article","created":{"date-parts":[[2016,11,9]],"date-time":"2016-11-09T13:36:49Z","timestamp":1478698609000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Deterministic (\u0394 + 1)-Coloring in Sublinear (in \u0394) Time in Static, Dynamic, and Faulty Networks"],"prefix":"10.1145","volume":"63","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[{"name":"Open University of Israel, Raanana"}]}],"member":"320","published-online":{"date-parts":[[2016,11,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400757"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536432"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835797"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993825"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_2_1_9_1","unstructured":"J. Bertrand. 1845. Memoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu\u2019elle renferme. Journal de l\u2019Ecole Royale Polytechnique 30 18 (1845) 123--140.  J. Bertrand. 1845. Memoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu\u2019elle renferme. Journal de l\u2019Ecole Royale Polytechnique 30 18 (1845) 123--140."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370","author":"Elkin M."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772959"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611467"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332464"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03850-6_14"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993814"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS). 44","author":"Kothapalli K."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21934"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.   D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_29_1","first-page":"366","article-title":"Memoire sur les nombres premiers","volume":"1","author":"Tchebychev P.","year":"1852","journal-title":"Journal de Mathmatiques Pures et Appliques."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167156"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2979675","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2979675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:35Z","timestamp":1750222475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2979675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,8]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,12,20]]}},"alternative-id":["10.1145\/2979675"],"URL":"https:\/\/doi.org\/10.1145\/2979675","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,8]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}