{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T01:46:41Z","timestamp":1782697601321,"version":"3.54.5"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T00:00:00Z","timestamp":1775260800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T00:00:00Z","timestamp":1775260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00446-025-00501-y","type":"journal-article","created":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T07:26:35Z","timestamp":1775287595000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved all-pairs approximate shortest paths in congested clique"],"prefix":"10.1007","volume":"39","author":[{"given":"Hong Duc","family":"Bui","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shashwat","family":"Chandra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi-Jun","family":"Chang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Dory","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dean","family":"Leitersdorf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,4,4]]},"reference":[{"issue":"4","key":"501_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM (JACM) 42(4), 844\u2013856 (1995)","journal-title":"Journal of the ACM (JACM)"},{"key":"501_CR2","doi-asserted-by":"crossref","unstructured":"Bui, H.\u00a0D., Chandra, S., Chang, Y.-J., Dory, M., Leitersdorf, D.: Improved all-pairs approximate shortest paths in congested clique. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 391\u2013400, (2024)","DOI":"10.1145\/3662158.3662804"},{"issue":"6","key":"501_CR3","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s00446-020-00380-5","volume":"34","author":"K Censor-Hillel","year":"2021","unstructured":"Censor-Hillel, K., Dory, M., Korhonen, J.H., Leitersdorf, D.: Fast approximate shortest paths in the congested clique. Distrib. Comput. 34(6), 463\u2013487 (2021)","journal-title":"Distrib. Comput."},{"key":"501_CR4","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Even, T., Flin, M., Halld\u00f3rsson, M.M.: When MIS and maximal matching are easy in the congested clique. In International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 194\u2013210. Springer, (2025)","DOI":"10.1007\/978-3-031-91736-3_12"},{"key":"501_CR5","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., 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), pp. 471\u2013480, (2019)","DOI":"10.1145\/3293611.3331607"},{"key":"501_CR6","unstructured":"Censor-Hillel, K., Fischer, O., Gonen, T., Le Gall, F., Leitersdorf, D., Oshman, R.: Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1\u201333:17, Dagstuhl, Germany, (2020). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"6","key":"501_CR7","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00446-016-0270-2","volume":"32","author":"K Censor-Hillel","year":"2019","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. Distrib. Comput. 32(6), 461\u2013478 (2019)","journal-title":"Distrib. Comput."},{"key":"501_CR8","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Leitersdorf, D., Turner, E.: Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model. In: Cao, J., Ellen, F., Rodrigues, L., Ferreira, B. (eds.) Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. Dagstuhl, Germany (2019)","DOI":"10.1016\/j.tcs.2019.11.006"},{"key":"501_CR9","doi-asserted-by":"crossref","unstructured":"Chechik, S., Zhang, T.: Constant-round near-optimal spanners in congested clique. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pp. 325\u2013334, New York, NY, USA, (2022). Association for Computing Machinery","DOI":"10.1145\/3519270.3538439"},{"key":"501_CR10","doi-asserted-by":"crossref","unstructured":"Dory, M., Fischer, O., Khoury, S., Leitersdorf, D.: Constant-round spanners and shortest paths in congested clique and MPC. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC), pp. 223\u2013233, New York, NY, USA, (2021). Association for Computing Machinery","DOI":"10.1145\/3465084.3467928"},{"issue":"5","key":"501_CR11","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"key":"501_CR12","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC), pp. 367\u2013376, (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"4","key":"501_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3527213","volume":"69","author":"M Dory","year":"2022","unstructured":"Dory, M., Parter, M.: Exponentially faster shortest paths in the congested clique. Journal of the ACM (JACM) 69(4), 1\u201342 (2022)","journal-title":"Journal of the ACM (JACM)"},{"key":"501_CR14","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, T., Nowicki, K.: MST in $$O(1)$$ rounds of congested clique. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2620\u20132632. SIAM, (2018)","DOI":"10.1137\/1.9781611975031.167"},{"key":"501_CR15","doi-asserted-by":"crossref","unstructured":"Korhonen, J.H., Suomela, J.: Towards a complexity theory for the congested clique. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 163\u2013172, New York, NY, USA, (2018). Association for Computing Machinery","DOI":"10.1145\/3210377.3210391"},{"key":"501_CR16","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 938\u2013948. SIAM, (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"501_CR17","doi-asserted-by":"crossref","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC), pp. 42\u201350, New York, NY, USA, (2013). Association for Computing Machinery","DOI":"10.1145\/2484239.2501983"},{"key":"501_CR18","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-662-53426-7_5","volume-title":"Distributed Computing","author":"F Le Gall","year":"2016","unstructured":"Le Gall, F.: Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In: Gavoille, C., Ilcinkas, D. (eds.) Distributed Computing, pp. 57\u201370. Springer, Berlin, Heidelberg (2016)"},{"issue":"1","key":"501_CR19","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in $$O(\\log \\log n)$$ communication rounds. SIAM J. Comput. 35(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"key":"501_CR20","unstructured":"Nazari, Y.: Sparse Hopsets in Congested Clique. In: Felber, P., Friedman, R., Gilbert, S., Miller, A.: editors, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), volume 153 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 34:1\u201334:16, Dagstuhl, Germany, (2020). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"key":"501_CR21","doi-asserted-by":"crossref","unstructured":"Nowicki, K.: A deterministic algorithm for the MST problem in constant rounds of congested clique. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1154\u20131165, New York, NY, USA, (2021). Association for Computing Machinery","DOI":"10.1145\/3406325.3451136"},{"key":"501_CR22","doi-asserted-by":"crossref","unstructured":"Ullman, J., Yannakakis, M.: High-probability parallel transitive closure algorithms. In Proceedings of the 2nd annual ACM symposium on Parallel algorithms and architectures (SPAA), pp. 200\u2013209, (1990)","DOI":"10.1145\/97444.97686"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00501-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00501-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00501-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T01:39:10Z","timestamp":1782697150000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00501-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,4]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["501"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00501-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,4]]},"assertion":[{"value":"29 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2026","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 competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13"}}