{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:45:49Z","timestamp":1749825949402,"version":"3.37.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T00:00:00Z","timestamp":1736467200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T00:00:00Z","timestamp":1736467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Icelandic Research Fund","award":["2310015-051"],"award-info":[{"award-number":["2310015-051"]}]},{"name":"David R. Cheriton Graduate Scholarship"},{"name":"Sloan Research Fellowship"},{"name":"NSERC Discovery grant"},{"DOI":"10.13039\/501100004490","name":"University of Waterloo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004490","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s00446-024-00475-3","type":"journal-article","created":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T09:04:05Z","timestamp":1736499845000},"page":"19-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["($$\\Delta + 1$$) vertex coloring in O(n) communication"],"prefix":"10.1007","volume":"38","author":[{"given":"Maxime","family":"Flin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Parth","family":"Mittal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,10]]},"reference":[{"issue":"5","key":"475_CR1","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. Assoc. Comput. Mach. 41(5), 960\u2013981 (1994). https:\/\/doi.org\/10.1145\/185675.306789","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"475_CR2","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s004930070013","volume":"20","author":"S Khanna","year":"2000","unstructured":"Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica 20(3), 393\u2013415 (2000). https:\/\/doi.org\/10.1007\/s004930070013","journal-title":"Combinatorica"},{"key":"475_CR3","doi-asserted-by":"publisher","unstructured":"Assadi, S., Chen, Y., Khanna, S.: Sublinear algorithms for $$(\\Delta +1)$$ vertex coloring. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 767\u2013786. SIAM, Philadelphia, PA (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.48","DOI":"10.1137\/1.9781611975482.48"},{"issue":"1","key":"475_CR4","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/0221015","journal-title":"SIAM J. Comput."},{"issue":"3","key":"475_CR5","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 20\u201345 (2016). https:\/\/doi.org\/10.1145\/2903137","journal-title":"J. ACM"},{"issue":"3","key":"475_CR6","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1137\/19M1249527","volume":"49","author":"Y-J Chang","year":"2020","unstructured":"Chang, Y.-J., Li, W., Pettie, S.: Distributed $$(\\Delta +1)$$-coloring via ultrafast graph shattering. SIAM J. Comput. 49(3), 497\u2013539 (2020). https:\/\/doi.org\/10.1137\/19M1249527","journal-title":"SIAM J. Comput."},{"key":"475_CR7","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Kuhn, F.: Deterministic distributed vertex coloring: simpler, faster, and without network decomposition. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2021, pp. 1009\u20131020. IEEE Computer Soc., Los Alamitos, CA (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00101","DOI":"10.1109\/FOCS52979.2021.00101"},{"key":"475_CR8","doi-asserted-by":"publisher","unstructured":"Chang, Y., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The complexity of ($$\\Delta $$+1) coloring in congested clique, massively parallel computation, and centralized local computation. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pp. 471\u2013480. ACM, New York, NY (2019). https:\/\/doi.org\/10.1145\/3293611.3331607","DOI":"10.1145\/3293611.3331607"},{"issue":"5","key":"475_CR9","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1137\/20M1366502","volume":"50","author":"A Czumaj","year":"2021","unstructured":"Czumaj, A., Davies, P., Parter, M.: Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM J. Comput. 50(5), 1603\u20131626 (2021). https:\/\/doi.org\/10.1137\/20M1366502","journal-title":"SIAM J. Comput."},{"key":"475_CR10","doi-asserted-by":"publisher","unstructured":"Bhattacharya, S., Chakrabarty, D., Henzinger, M., Nanongkai, D.: Dynamic algorithms for graph coloring. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pp. 1\u201320. SIAM, Philadelphia, PA (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.1","DOI":"10.1137\/1.9781611975031.1"},{"issue":"2","key":"475_CR11","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/3494539","volume":"18","author":"S Bhattacharya","year":"2022","unstructured":"Bhattacharya, S., Grandoni, F., Kulkarni, J., Liu, Q.C., Solomon, S.: Fully dynamic $$(\\Delta + 1)$$-coloring in $$O(1)$$ update time. ACM Trans. Algorithms 18(2), 10\u201325 (2022). https:\/\/doi.org\/10.1145\/3494539","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"475_CR12","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/3501403","volume":"18","author":"M Henzinger","year":"2022","unstructured":"Henzinger, M., Peng, P.: Constant-time dynamic $$(\\Delta + 1)$$-coloring. ACM Trans. Algorithms 18(2), 16\u201321 (2022). https:\/\/doi.org\/10.1145\/3501403","journal-title":"ACM Trans. Algorithms"},{"key":"475_CR13","doi-asserted-by":"publisher","unstructured":"Yao, A.C.: Some complexity questions related to distributive computing (preliminary report). In: Fischer, M.J., DeMillo, R.A., Lynch, N.A., Burkhard, W.A., Aho, A.V. (eds.) Proceedings of the Eleventh Annual ACM Symposium on Theory Of Computing, pp. 209\u2013213. ACM, New York, NY (1979). https:\/\/doi.org\/10.1145\/800135.804414","DOI":"10.1145\/800135.804414"},{"key":"475_CR14","first-page":"189","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity, p. 189. Cambridge University Press, Cambridge (1997)"},{"key":"475_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1017\/9781108671644","volume-title":"Communication Complexity and Applications","author":"A Rao","year":"2020","unstructured":"Rao, A., Yehudayoff, A.: Communication Complexity and Applications, p. 251. Cambridge University Press, Cambridge (2020)"},{"key":"475_CR16","doi-asserted-by":"publisher","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: STOC\u201911\u2014Proceedings of the 43rd ACM Symposium on Theory Of Computing, pp. 363\u2013372. ACM, New York, NY (2011). https:\/\/doi.org\/10.1145\/1993636.1993686","DOI":"10.1145\/1993636.1993686"},{"key":"475_CR17","doi-asserted-by":"publisher","unstructured":"Bachrach, N., Censor-Hillel, K., Dory, M., Efron, Y., Leitersdorf, D., Paz, A.: Hardness of distributed optimization. In: Robinson, P., Ellen, F. (eds.) Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pp. 238\u2013247. ACM, New York, NY (2019). https:\/\/doi.org\/10.1145\/3293611.3331597","DOI":"10.1145\/3293611.3331597"},{"key":"475_CR18","doi-asserted-by":"publisher","unstructured":"Indyk, P., Woodruff, D.P.: Tight lower bounds for the distinct elements problem. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pp. 283\u2013288. IEEE Computer Society, Los Alamitos, CA (2003). https:\/\/doi.org\/10.1109\/SFCS.2003.1238202","DOI":"10.1109\/SFCS.2003.1238202"},{"key":"475_CR19","doi-asserted-by":"publisher","unstructured":"Chakrabarti, A., Regev, O.: An optimal lower bound on the communication complexity of gap-Hamming-distance. SIAM J. Comput. 41(5), 1299\u20131317 (2012). https:\/\/doi.org\/10.1137\/120861072. arXiv:1009.3460","DOI":"10.1137\/120861072"},{"key":"475_CR20","doi-asserted-by":"publisher","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. 57, 37\u201349 (1998). https:\/\/doi.org\/10.1006\/jcss.1998.1577. 27th Annual ACM Symposium on the Theory of Computing (STOC &95) (Las Vegas, NV)","DOI":"10.1006\/jcss.1998.1577"},{"issue":"2","key":"475_CR21","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M Karchmer","year":"1990","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3(2), 255\u2013265 (1990). https:\/\/doi.org\/10.1137\/0403021","journal-title":"SIAM J. Discrete Math."},{"key":"475_CR22","doi-asserted-by":"publisher","unstructured":"Assadi, S., Dudeja, A.: A simple semi-streaming algorithm for global minimum cuts. In: Le, H.V., King, V. (eds.) 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pp. 172\u2013180. SIAM, Philadelphia, PA (2021). https:\/\/doi.org\/10.1137\/1.9781611976496.19","DOI":"10.1137\/1.9781611976496.19"},{"key":"475_CR23","doi-asserted-by":"publisher","unstructured":"Blikstad, J., Brand, J., Efron, Y., Mukhopadhyay, S., Nanongkai, D.: Nearly optimal communication and query complexity of bipartite matching. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science\u2014FOCS 2022, pp. 1174\u20131185. IEEE Computer Soc., Los Alamitos, CA (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00113","DOI":"10.1109\/FOCS54457.2022.00113"},{"key":"475_CR24","doi-asserted-by":"publisher","unstructured":"Hajnal, A., Maass, W., Tur\u00e1n, G.: On the communication complexity of graph properties. In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pp. 186\u2013191. ACM, New York, NY (1988). https:\/\/doi.org\/10.1145\/62212.62228","DOI":"10.1145\/62212.62228"},{"key":"475_CR25","doi-asserted-by":"publisher","unstructured":"Assadi, S., Chakrabarti, A., Ghosh, P., Stoeckl, M.: Coloring in graph streams via deterministic and adversarially robust algorithms. In: Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023, Seattle, WA, USA, June 18-23, 2023, pp. 141\u2013153. ACM, New York, NY (2023). https:\/\/doi.org\/10.1145\/3584372.3588681","DOI":"10.1145\/3584372.3588681"},{"issue":"2","key":"475_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I Newman","year":"1991","unstructured":"Newman, I.: Private versus common random bits in communication complexity. Inform. Process. Lett. 39(2), 67\u201371 (1991). https:\/\/doi.org\/10.1016\/0020-0190(91)90157-D","journal-title":"Inform. Process. Lett."},{"issue":"9","key":"475_CR27","doi-asserted-by":"publisher","first-page":"827","DOI":"10.4169\/amer.math.monthly.124.9.827","volume":"124","author":"Y Zhao","year":"2017","unstructured":"Zhao, Y.: Extremal regular graphs: independent sets and graph homomorphisms. Amer. Math. Monthly 124(9), 827\u2013843 (2017). https:\/\/doi.org\/10.4169\/amer.math.monthly.124.9.827","journal-title":"Amer. Math. Monthly"},{"key":"475_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009). https:\/\/doi.org\/10.1017\/CBO9780511581274"},{"key":"475_CR29","doi-asserted-by":"publisher","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Natural Computing Series, pp. 1\u201387. Springer, Switzerland AG (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4_1","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"475_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0865-5_26","volume-title":"The collected works of Wassily Hoeffding","author":"W Hoeffding","year":"1994","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. In: The collected works of Wassily Hoeffding. Springer, New York (1994). https:\/\/doi.org\/10.1007\/978-1-4612-0865-5_26"},{"issue":"4","key":"475_CR31","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. 5(4), 545\u2013557 (1992). https:\/\/doi.org\/10.1137\/0405044","journal-title":"SIAM J. Discrete Math."},{"key":"475_CR32","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2001","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, Hoboken (2001). https:\/\/doi.org\/10.1002\/0471200611"},{"key":"475_CR33","unstructured":"Mande, N.S., Paraashar, M., Sanyal, S., Saurabh, N.: On the communication complexity of finding a king in a tournament. Accepted at RANDOM 2024 (2024)"},{"issue":"3","key":"475_CR34","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: Three short proofs in graph theory. J. Combinatorial Theory Ser. B 19(3), 269\u2013271 (1975). https:\/\/doi.org\/10.1016\/0095-8956(75)90089-1","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"475_CR35","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2024.7","author":"S Assadi","year":"2024","unstructured":"Assadi, S., Ghosh, P., Loff, B., Mittal, P., Mukhopadhyay, S.: Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.CCC.2024.7","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"1","key":"475_CR36","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"N Nisan","year":"1993","unstructured":"Nisan, N., Wigderson, A.: Rounds in communication complexity revisited. SIAM J. Comput. 22(1), 211\u2013219 (1993). https:\/\/doi.org\/10.1137\/0222016","journal-title":"SIAM J. Comput."},{"key":"475_CR37","doi-asserted-by":"publisher","unstructured":"Saglam, M., Tardos, G.: On the communication complexity of sparse set disjointness and exists-equal problems. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 678\u2013687. IEEE Computer Society, Los Alamitos, CA (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.78","DOI":"10.1109\/FOCS.2013.78"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00475-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-024-00475-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00475-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T11:39:36Z","timestamp":1739533176000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-024-00475-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,10]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["475"],"URL":"https:\/\/doi.org\/10.1007\/s00446-024-00475-3","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,1,10]]},"assertion":[{"value":"1 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}