{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:46:57Z","timestamp":1787510817139,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662534250","type":"print"},{"value":"9783662534267","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53426-7_8","type":"book-chapter","created":{"date-parts":[[2016,9,3]],"date-time":"2016-09-03T04:49:15Z","timestamp":1472878155000},"page":"99-113","source":"Crossref","is-referenced-by-count":10,"title":["Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model"],"prefix":"10.1007","author":[{"given":"Dan","family":"Hefetz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,9,4]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Hefetz, D., Kuhn, F., Maus, Y., Steger, A.: A polynomial lower bound for distributed graph coloring in a weak LOCAL model. CoRR, abs\/1607.05212 (2016)","DOI":"10.1007\/978-3-662-53426-7_8"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of the Symposium on Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"8_CR3","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers (2013)","DOI":"10.2200\/S00520ED1V01Y201307DCT011"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L.: Deterministic ( $$\\Delta $$ + 1)-coloring in sublinear (in $$\\Delta $$ ) time in static, dynamic and faulty networks. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pp. 345\u2013354 (2015)","DOI":"10.1145\/2767386.2767410"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Heinrich, M., Kosowski, A.: Local conflict coloring. CoRR, abs\/1511.01287 (2015)","DOI":"10.1109\/FOCS.2016.73"},{"issue":"1","key":"8_CR7","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"8_CR8","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00446-013-0202-3","volume":"28","author":"L Hella","year":"2015","unstructured":"Hella, L., J\u00e4rvisalo, M., Kuusisto, A., Laurinharju, J., Lampi\u00e4inen, T., Luosto, K., Suomela, J., Virtema, J.: Weak models of distributed computing, with connections to modal logic. Distrib. Comput. 28(1), 31\u201353 (2015)","journal-title":"Distrib. Comput."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC), pp. 7\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"issue":"1","key":"8_CR10","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986)","journal-title":"Inf. Control"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"issue":"2","key":"8_CR12","first-page":"581","volume":"20","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581\u2013592 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"8_CR13","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2015","unstructured":"Barenboim, L., Elkin, M., Kuhn, F.: Distributed (Delta+1)-coloring in linear (in Delta) time. SIAM J. Comput. 43(1), 72\u201395 (2015)","journal-title":"SIAM J. Comput."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proceedings of the 29th Symposium on Principles of Distributed Computing (PODC) (2010)","DOI":"10.1145\/1835698.1835797"},{"issue":"4","key":"8_CR15","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. In Proceedings of the 53rd Symposium on Foundations of Computer Science (FOCS) (2012)","DOI":"10.1109\/FOCS.2012.60"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Harris, S.G., Schneider, J., Su, H.-H.: Distributed ( $$\\Delta +1$$ )-coloring in sublogarithmic rounds. In: Proceedings of the 48th Symposium on the Theory of Computing (STOC) (2016)","DOI":"10.1145\/2897518.2897533"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. CoRR, abs\/1602.08166 (2016)","DOI":"10.1109\/FOCS.2016.72"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Brand, S., Fischer, O., Hirvonen, J., Keller, B., Lempi\u00e4inen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed Lov\u00e1sz local lemma. In: Proceedings of the 48th Symposium on the Theory of Computing (STOC) (2016)","DOI":"10.1145\/2897518.2897570"},{"issue":"6","key":"8_CR21","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s00446-013-0194-z","volume":"27","author":"M G\u00f6\u00f6s","year":"2014","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: No sublogarithmic-time approximation scheme for bipartite vertex cover. Distrib. Comput. 27(6), 435\u2013443 (2014)","journal-title":"Distrib. Comput."},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Linear-in-Delta lower bounds in the LOCAL model. In: Proceedings of the 33rd Symposium on Principles of Distributed Computing (PODC), pp. 86\u201395 (2014)","DOI":"10.1145\/2611462.2611467"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd Symposium on Principles of Distributed Computing (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"8_CR24","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2) (2016). http:\/\/dl.acm.org\/citation.cfm?id=2742012 . Article No. 17"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/978-3-642-16367-8_14","volume-title":"Property Testing","author":"N Alon","year":"2010","unstructured":"Alon, N.: On constant time approximation of parameters of bounded degree graphs. In: Goldreich, O. (ed.) Property Testing. LNCS, vol. 6390, pp. 234\u2013239. Springer, Heidelberg (2010)"},{"issue":"5","key":"8_CR26","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. Distr. Comput. 22(5), 363\u2013379 (2010)","journal-title":"Distr. Comput."},{"key":"8_CR27","unstructured":"Kuhn, F.: Local multicoloring algorithms: computing a nearly-optimal TDMA schedule in constant time. In: Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS), pp. 613\u2013624 (2009)"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Szegedy, M., Vishwanathan, S.: Locality based graph coloring. In: Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), pp. 201\u2013207 (1993)","DOI":"10.1145\/167088.167156"},{"key":"8_CR29","unstructured":"Gavoille, C., Klasing, R., Kosowski, A., Kuszner, \u0141., Navarra, A.: On the complexity of distributed graph coloring with local minimality constraints. Technical report 6399, INRIA (2007)"},{"key":"8_CR30","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53426-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T14:35:33Z","timestamp":1657204533000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53426-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662534250","9783662534267"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53426-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}