{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T02:18:28Z","timestamp":1772504308425,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,2,27]],"date-time":"2025-02-27T00:00:00Z","timestamp":1740614400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,27]],"date-time":"2025-02-27T00:00:00Z","timestamp":1740614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study the algorithmic problem of multiplying large matrices that are rectangular.\n  We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give algorithms with complexity <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n^{p + 1}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mo>+<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n \\times n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> by <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n \\times n^p$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mi>p<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> matrix multiplication. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. \n  In particular, we prove that any lower bound on the dual exponent of matrix multiplication <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\alpha$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b1<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> via the big Coppersmith-Winograd tensors cannot exceed <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$0.6218$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>0.6218<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00037-025-00264-9","type":"journal-article","created":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T21:20:43Z","timestamp":1740604843000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Barriers for rectangular matrix multiplication"],"prefix":"10.1007","volume":"34","author":[{"given":"Matthias","family":"Christandl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois Le","family":"Gall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Lysikov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeroen","family":"Zuiddam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,27]]},"reference":[{"key":"264_CR1","unstructured":"Josh Alman (2019). Limits on the Universal Method for Matrix\nMultiplication. In Proceedings of the 34th Computational Complexity\nConference (CCC 2019), 12:1\u201312:24. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2019.12."},{"key":"264_CR2","doi-asserted-by":"crossref","unstructured":"Josh Alman, Ran Duan, Virginia Vassilevska Williams,\nYinzhan Xu, Zixuan Xu & Renfei Zhou (2025). More Asymmetry\nYields Faster Matrix Multiplication. In Proceedings of the\n2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\n2025), 2005\u20132039. URL https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611978322.63.","DOI":"10.1137\/1.9781611978322.63"},{"key":"264_CR3","unstructured":"Josh Alman & Virginia Vassilevska Williams (2018a). Further\nLimitations of the Known Approaches for Matrix Multiplication. In\nProceedings of the 9th Innovations in Theoretical Computer Science\nConference (ITCS 2018), 25:1\u201325:15. ISBN 978-3-95977-060-6. ISSN\n1868-8969."},{"key":"264_CR4","doi-asserted-by":"crossref","unstructured":"Josh Alman & Virginia Vassilevska Williams (2018b). Limits on\nAll Known (and Some Unknown) Approaches to Matrix Multiplication.\nIn Proceedings of the 59th Annual IEEE Symposium on Foundations of\nComputer Science (FOCS 2018), 580\u2013591. ISSN 2575-8454.","DOI":"10.1109\/FOCS.2018.00061"},{"key":"264_CR5","doi-asserted-by":"crossref","unstructured":"Josh Alman & Virginia Vassilevska Williams (2021). A Refined\nLaser Method and Faster Matrix Multiplication. In Proceedings of the\n2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021),\n522\u2013539. URL https:\/\/doi.org\/10.1137\/1.9781611976465.32.","DOI":"10.1137\/1.9781611976465.32"},{"key":"264_CR6","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Yuval Filmus & Fran\u00e7is Le Gall (2015).\nFast matrix multiplication: limitations of the Coppersmith-Winograd\nmethod (extended abstract). In Proceedings of the 47th Annual ACM\nSymposium on Theory of Computing (STOC 2015), 585\u2013593.","DOI":"10.1145\/2746539.2746554"},{"key":"264_CR7","unstructured":"Markus Bl\u00e4ser (2013). Fast Matrix Multiplication. Number 5 in\nGraduate Surveys. Theory of Computing Library, 1\u201360 ."},{"key":"264_CR8","unstructured":"Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow,\nEric Naslund, William F. Sawin & Chris Umans (2017a).\nOn cap sets and the group-theoretic approach to matrix multiplication.\nDiscrete Anal. ISSN 2397-3129."},{"key":"264_CR9","unstructured":"Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A Grochow\n& Chris Umans (2017b). Which groups are amenable to proving\nexponent two for matrix multiplication? URL https:\/\/arxiv.org\/abs\/1712.02302."},{"key":"264_CR10","doi-asserted-by":"crossref","unstructured":"Jan van den Brand (2020). A Deterministic Linear Program Solver in\nCurrent Matrix Multiplication Time. In Proceedings of the 2020 ACMSIAM\nSymposium on Discrete Algorithms (SODA 2020), 259\u2013278. URL\nhttps:\/\/doi.org\/10.1137\/1.9781611975994.16..","DOI":"10.1137\/1.9781611975994.16"},{"key":"264_CR11","unstructured":"Peter B\u00fcrgisser, Michael Clausen & M. Amin Shokrollahi\n(1997). Algebraic complexity theory, volume 315 of Grundlehren Math.\nWiss. Springer-Verlag, Berlin. ISBN 3-540-60582-7, xxiv+618 ."},{"key":"264_CR12","doi-asserted-by":"crossref","unstructured":"Matthias Christandl, P\u00e9ter Vrana & Jeroen Zuiddam (2018).\nUniversal points in the asymptotic spectrum of tensors. In Proceedings\nof the 50th Annual ACM Symposium on Theory of Computing (STOC\n2018), 289\u2013296. URL https:\/\/doi.org\/10.1145\/3188745.3188766.","DOI":"10.1145\/3188745.3188766"},{"key":"264_CR13","unstructured":"Matthias Christandl, P\u00e9ter Vrana & Jeroen Zuiddam (2019).\nBarriers for Fast Matrix Multiplication from Irreversibility. In Proceedings\nof the 34th Computational Complexity Conference (CCC 2019),\n26:1\u201326:17. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2019.26."},{"key":"264_CR14","doi-asserted-by":"crossref","unstructured":"Michael B. Cohen, Yin Tat Lee & Zhao Song (2019). Solving\nLinear Programs in the Current Matrix Multiplication Time. In Proceedings\nof the 51st Annual ACM Symposium on Theory of Computing\n(STOC 2019), 938-942. ISBN 9781450367059.","DOI":"10.1145\/3313276.3316303"},{"key":"264_CR15","doi-asserted-by":"crossref","unstructured":"Don Coppersmith (1982). Rapid Multiplication of Rectangular Matrices.\nSIAM J. Comput. 11(3), 467\u2013471. URL https:\/\/doi.org\/10.1137\/0211037.","DOI":"10.1137\/0211037"},{"key":"264_CR16","doi-asserted-by":"crossref","unstructured":"Don Coppersmith (1997). Rectangular Matrix Multiplication Revisited.\nJ. Complexity 13(1), 42\u201349. URL https:\/\/doi.org\/10.1006\/jcom.1997.0438.","DOI":"10.1006\/jcom.1997.0438"},{"key":"264_CR17","doi-asserted-by":"crossref","unstructured":"Don Coppersmith & Shmuel Winograd (1990). Matrix Multiplication\nvia Arithmetic Progressions. J. Symb. Comput. 9(3), 251\u2013280.\nURL https:\/\/doi.org\/10.1016\/S0747-7171(08)80013-2.","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"264_CR18","unstructured":"Steven Diamond & Stephen Boyd (2016). CVXPY: A Pythonembedded\nmodeling language for convex optimization. Journal of Machine\nLearning Research 17(83), 1\u20135. URL https:\/\/www.cvxpy.org."},{"key":"264_CR19","doi-asserted-by":"crossref","unstructured":"Ran Duan, Hongxun Wu & Renfei Zhou (2023). Faster Matrix\nMultiplication via Asymmetric Hashing. In Proceedings of the 64th\nIEEE Annual Symposium on Foundations of Computer Science (FOCS\n2023), 2129\u20132138. URL https:\/\/doi.org\/10.1109\/FOCS57990.2023.00130.","DOI":"10.1109\/FOCS57990.2023.00130"},{"key":"264_CR20","doi-asserted-by":"crossref","unstructured":"Xiaohan Huang & Victor Y. Pan (1998). Fast Rectangular Matrix\nMultiplication and Applications. J. Complexity 14(2), 257\u2013299.","DOI":"10.1006\/jcom.1998.0476"},{"key":"264_CR21","doi-asserted-by":"crossref","unstructured":"ShanXue Ke, BenSheng Zeng, WenBao Han & Victor Y. Pan\n(2008). Fast rectangular matrix multiplication and some applications.\nScience in China Series A: Mathematics 51(3), 389\u2013406.","DOI":"10.1007\/s11425-007-0169-2"},{"key":"264_CR22","doi-asserted-by":"crossref","unstructured":"Fran\u00e7is Le Gall & Florent Urrutia (2018). Improved Rectangular\nMatrix Multiplication using Powers of the Coppersmith-Winograd\nTensor. In Proceedings of the 29th Annual ACM-SIAM Symposium on\nDiscrete Algorithms (SODA 2018), 1029\u20131046. URL https:\/\/doi.org\/10.1137\/1.9781611975031.67.","DOI":"10.1137\/1.9781611975031.67"},{"key":"264_CR23","doi-asserted-by":"crossref","unstructured":"Fran\u00e7is Le Gall (2012). Faster algorithms for rectangular matrix\nmultiplication. In Proceedings of the 53rd Annual IEEE Symposium on\nFoundations of Computer Science (FOCS 2012), 514\u2013523.","DOI":"10.1109\/FOCS.2012.80"},{"key":"264_CR24","doi-asserted-by":"crossref","unstructured":"Fran\u00e7is Le Gall (2014). Powers of tensors and fast matrix multiplication.\nIn Proceedings of the 39th International Symposium on Symbolic\nand Algebraic Computation (ISSAC 2014), 296\u2013303.","DOI":"10.1145\/2608628.2608664"},{"key":"264_CR25","doi-asserted-by":"crossref","unstructured":"Fran\u00e7is Le Gall (2024). Faster Rectangular Matrix Multiplication\nby Combination Loss Analysis. In Proceedings of the 2024 ACM-SIAM\nSymposium on Discrete Algorithms (SODA 2024), 3765\u20133791. URL\nhttps:\/\/doi.org\/10.1137\/1.9781611977912.133.","DOI":"10.1137\/1.9781611977912.133"},{"key":"264_CR26","unstructured":"Yin Tat Lee, Zhao Song & Qiuyi Zhang (2019). Solving Empirical\nRisk Minimization in the Current Matrix Multiplication Time. In Conference\non Learning Theory (COLT 2019), 2140\u20132157. URL http:\/\/proceedings.mlr.press\/v99\/lee19a.html."},{"key":"264_CR27","doi-asserted-by":"crossref","unstructured":"Grazia Lotti & Francesco Romani (1983). On the Asymptotic\nComplexity of Rectangular Matrix Multiplication. Theor.\nComput. Sci. 23, 171\u2013185. URL https:\/\/doi.org\/10.1016\/0304-3975(83)90054-3.","DOI":"10.1016\/0304-3975(83)90054-3"},{"key":"264_CR28","unstructured":"Andrew James Stothers (2010). On the complexity of matrix multiplication.\nPh.D. thesis, University of Edinburgh. URL http:\/\/hdl.handle.net\/1842\/4734."},{"key":"264_CR29","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1969). Gaussian elimination is not optimal. Numerische\nMathematik 13(4), 354\u2013356.","DOI":"10.1007\/BF02165411"},{"key":"264_CR30","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1987). Relative bilinear complexity and matrix\nmultiplication. J. reine angew. Math. 375\/376, 406\u2013443.","DOI":"10.1515\/crll.1987.375-376.406"},{"key":"264_CR31","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1988). The asymptotic spectrum of tensors. J.\nreine angew. Math. 384, 102\u2013152.","DOI":"10.1515\/crll.1988.384.102"},{"key":"264_CR32","doi-asserted-by":"crossref","unstructured":"Volker Strassen (1991). Degeneration and complexity of bilinear\nmaps: some asymptotic spectra. J. reine angew. Math. 413, 127\u2013180.\nISSN 0075-4102.","DOI":"10.1515\/crll.1991.413.127"},{"key":"264_CR33","doi-asserted-by":"crossref","unstructured":"Virginia Vassilevska Williams (2012). Multiplying matrices faster\nthan Coppersmith-Winograd (extended abstract). In Proceedings of the\n44th Annual ACM Symposium on Theory of Computing (STOC 2012),\n887\u2013898.","DOI":"10.1145\/2213977.2214056"},{"key":"264_CR34","doi-asserted-by":"crossref","unstructured":"Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu & Renfei\nZhou (2024). New Bounds for Matrix Multiplication: from Alpha\nto Omega. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete\nAlgorithms (SODA 2024), 3792\u20133835.","DOI":"10.1137\/1.9781611977912.134"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00264-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00264-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00264-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T23:10:33Z","timestamp":1753139433000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00264-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,27]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["264"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00264-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,27]]},"assertion":[{"value":"15 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}