Limits on the Universal Method for Matrix Multiplication

by Josh Alman

Theory of Computing, Volume 17(1), pp. 1-30, 2021

Bibliography with links to cited articles

[1]   Josh Alman: Limits on the Universal Method for matrix multiplication. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 12:1–12:24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.12]

[2]   Josh Alman and Virginia Vassilevska Williams: Further limitations of the known approaches for matrix multiplication. In Proc. 9th Innovations in Theoret. Comp. Sci. conf. (ITCS’18), pp. 25:1–25:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.25]

[3]    Josh Alman and Virginia Vassilevska Williams: Limits on all known (and some unknown) approaches to matrix multiplication. In Proc. 59th FOCS, pp. 580–591. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00061]

[4]   Josh Alman and Virginia Vassilevska Williams: A refined laser method and faster matrix multiplication. In Proc. 32nd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’21), pp. 522–539. SIAM, 2021. [doi:10.1137/1.9781611976465.32]

[5]   Noga Alon, Amir Shpilka, and Christopher Umans: On sunflowers and matrix multiplication. Comput. Complexity, 22(2):219–243, 2013. [doi:10.1007/s00037-013-0060-1]

[6]   Andris Ambainis, Yuval Filmus, and François Le Gall: Fast matrix multiplication: limitations of the Coppersmith–Winograd method. In Proc. 47th STOC, pp. 585–593. ACM Press, 2015. [doi:10.1145/2746539.2746554]

[7]   Dario Bini: Border rank of a p × q × 2 tensor and the optimal approximation of a pair of bilinear forms. In Proc. 7th Internat. Colloq. on Automata, Languages, and Programming (ICALP’80), pp. 98–108. Springer, 1980. [doi:10.1007/3-540-10003-2_63]

[8]   Markus Bläser: Fast Matrix Multiplication. Number 5 in Graduate Surveys. Theory of Computing Library, 2013. [doi:10.4086/toc.gs.2013.005]

[9]   Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans: On cap sets and the group-theoretic approach to matrix multiplication. Discrete Analysis, 2017:3:1–27. [doi:10.19086/da.1245]

[10]   Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, and Chris Umans: Which groups are amenable to proving exponent two for matrix multiplication? 2017. [arXiv:1712.02302]

[11]   Peter Bürgisser, Michael Clausen, and Mohammad A. Shokrollahi: Algebraic Complexity Theory. Volume 315 of Grundlehren der Math. Wiss. Springer, 2013. [doi:doi:10.1007/978-3-662-03338-8]

[12]   Matthias Christandl, Péter Vrana, and Jeroen Zuiddam: Universal points in the asymptotic spectrum of tensors. In Proc. 50th STOC, pp. 289–296. ACM Press, 2018. [doi:10.1145/3188745.3188766]

[13]   Matthias Christandl, Péter Vrana, and Jeroen Zuiddam: Barriers for fast matrix multiplication from irreversibility. In Proc. 34th Comput. Complexity Conf. (CCC’19), volume 137, pp. 26:1–26:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.26]

[14]    Michael B. Cohen, Yin Tat Lee, and Zhao Song: Solving linear programs in the current matrix multiplication time. J. ACM, 68(1):3:1–3:39, 2021. Preliminary version in STOC’19. [doi:10.1145/3424305]

[15]   Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Christopher Umans: Group-theoretic algorithms for matrix multiplication. In Proc. 46th FOCS, pp. 379–388. IEEE Comp. Soc., 2005. [doi:10.1109/SFCS.2005.39, arXiv:math/0511460]

[16]   Henry Cohn and Christopher Umans: A group-theoretic approach to fast matrix multiplication. In Proc. 44th FOCS, pp. 438–449. IEEE Comp. Soc., 2003. [doi:10.1109/SFCS.2003.1238217]

[17]   Henry Cohn and Christopher Umans: Fast matrix multiplication using coherent configurations. In Proc. 24th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1074–1086. SIAM, 2013. [doi:10.1137/1.9781611973105.77]

[18]   Don Coppersmith and Shmuel Winograd: On the asymptotic complexity of matrix multiplication. SIAM J. Comput., 11(3):472–492, 1982. [doi:10.1137/0211038]

[19]   Don Coppersmith and Shmuel Winograd: Matrix multiplication via arithmetic progressions. J. Symbolic Comput., 9(3):251–280, 1990. [doi:10.1016/S0747-7171(08)80013-2]

[20]   Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach: Progression-free sets in Z4n are exponentially small. Ann. Math., 185(1):331–337, 2017. [doi:10.4007/annals.2017.185.1.7]

[21]   Alexander M. Davie and Andrew James Stothers: Improved bound for complexity of matrix multiplication. Proc. Royal Soc. Edinburgh, Sec. A, 143(2):351–369, 2013. [doi:10.1017/S0308210511001648]

[22]   Jordan S. Ellenberg and Dion Gijswijt: On large subsets of Fqn with no three-term arithmetic progression. Ann. Math., 185(1):339–343, 2017. [doi:10.4007/annals.2017.185.1.8]

[23]   Matti Karppa and Petteri Kaski: Probabilistic tensors and opportunistic Boolean matrix multiplication. In Proc. 30th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’19), pp. 496–515. SIAM, 2019. [doi:10.1137/1.9781611975482.31]

[24]   Robert Kleinberg, Will Sawin, and David Speyer: The growth rate of tri-colored sum-free sets. Discrete Analysis, 2018:12:1–10. [doi:10.19086/da.3734]

[25]   François Le Gall: Faster algorithms for rectangular matrix multiplication. In Proc. 53rd FOCS, pp. 514–523. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.80]

[26]   François Le Gall: Powers of tensors and fast matrix multiplication. In Proc. 39th Internat. Symp. Symbolic and Algebraic Computation (ISSAC’14), pp. 296–303. ACM Press, 2014. [doi:10.1145/2608628.2608664]

[27]   François Le Gall and Florent Urrutia: Improved rectangular matrix multiplication using powers of the Coppersmith–Winograd tensor. In Proc. 29th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1029–1046. SIAM, 2018. [doi:10.1137/1.9781611975031.67]

[28]   Eric Naslund and Will Sawin: Upper bounds for sunflower-free sets. In Forum of Mathematics, Sigma, volume 5, pp. e15:1–10. Cambridge Univ. Press, 2017. [doi:10.1017/fms.2017.12]

[29]   Arnold Schönhage: Partial and total matrix multiplication. SIAM J. Comput., 10(3):434–455, 1981. [doi:10.1137/0210032]

[30]   Volker Strassen: Gaussian elimination is not optimal. Numerische Mathematik, 13(4):354–356, 1969. [doi:10.1007/BF02165411]

[31]   Volker Strassen: The asymptotic spectrum of tensors and the exponent of matrix multiplication. In Proc. 27th FOCS, pp. 49–54. IEEE Comp. Soc., 1986. [doi:10.1109/SFCS.1986.52]

[32]   Volker Strassen: Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 1987(375–376):406–443, 1987. [doi:10.1515/crll.1987.375-376.406]

[33]   Volker Strassen: Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math., 1991(413):127–180, 1991. [doi:10.1515/crll.1991.413.127]

[34]   Terence Tao: A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound, 2016. LINK at terrytao.wordpress.com.

[35]   Terence Tao and Will Sawin: Notes on the “slice rank” of tensors., 2016. LINK at terrytao.wordpress.com.

[36]   Virginia Vassilevska Williams: Multiplying matrices faster than Coppersmith–Winograd. In Proc. 44th STOC, pp. 887–898. ACM Press, 2012. [doi:10.1145/2213977.2214056]