Barriers for Fast Matrix Multiplication from Irreversibility

by Matthias Christandl, Péter Vrana, and Jeroen Zuiddam

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

Bibliography with links to cited articles

[1]   Josh Alman: Limits on the universal method for matrix multiplication. Theory of Computing, 17(1):1–30, 2021. Preliminary version in CCC’19. [doi:10.4086/toc.2021.v017a001, arXiv:1812.08731]

[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–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, arXiv:1810.08671]

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

[5]   Felix A. Behrend: On sets of integers which contain no three terms in arithmetical progression. Proc. Nat. Acad. Sci. USA, 32(12):331–332, 1946. [doi:10.1073/pnas.32.12.331]

[6]   Charles H. Bennett, Sandu Popescu, Daniel Rohrlich, John A. Smolin, and Ashish V. Thapliyal: Exact and asymptotic measures of multipartite pure-state entanglement. Phys. Rev. A (3), 63(1):012307, 2000. [doi:10.1103/PhysRevA.63.012307]

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

[8]   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, 3:1–27, 2017. [doi:10.19086/da.1245, arXiv:1605.06702]

[9]   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]

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

[11]   Matthias Christandl, Franois Le Gall, Vladimir Lysikov, and Jeroen Zuiddam: Barriers for rectangular matrix multiplication, 2020. [arXiv:2003.03019]

[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, arXiv:1709.07851]

[13]   Matthias Christandl, Péter Vrana, and Jeroen Zuiddam: Asymptotic tensor rank of graph tensors: Beyond matrix multiplication. Comput. Complexity, 28(1):57–111, 2019. [doi:10.1007/s00037-018-0172-8, arXiv:1609.07476]

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

[15]   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]

[16]   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. ACM DL.

[17]   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]

[18]   Wolfgang Dür, Guivre Vidal, and Juan Ignacio Cirac: Three qubits can be entangled in two inequivalent ways. Phys. Rev. A (3), 62(6):062314, 12, 2000. [doi:10.1103/PhysRevA.62.062314]

[19]   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]

[20]   Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki: Quantum entanglement. Rev. Modern Physics, 81(2):865–942, 2009. [doi:10.1103/RevModPhys.81.865]

[21]   Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam: Geometric rank of tensors and subrank of matrix multiplication. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 35:1–19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.35, arXiv:2002.09472]

[22]   Joseph M. Landsberg and Mateusz Michaek: Abelian tensors. J. Math. Pures Appliques, 108(3):333–371, 2017. [doi:10.1016/j.matpur.2016.11.004, arXiv:1504.03732]

[23]   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]

[24]   George Pólya and Gabor Szeg˝o            : Problems and Theorems in Analysis I. Classics in Math. Springer, 1924/1972/1998. [doi:10.1007/978-3-642-61983-0]

[25]   Raphaël Salem and Donald Clayton Spencer: On sets of integers which contain no three terms in arithmetical progression. Proc. Nat. Acad. Sci. USA, 28(12):561–563, 1942. [doi:10.1073/pnas.28.12.561]

[26]   Will Sawin: Bounds for matchings in nonabelian groups. Electr. J. Combinat., 25(4), 2018. [doi:10.37236/7520, arXiv:1702.00905]

[27]   Andrew James Stothers: On the complexity of matrix multiplication. Ph. D. thesis, Univ. Edinburgh, 2010. era-handle.

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

[29]   Volker Strassen: Relative bilinear complexity and matrix multiplication. J. reine angew. Math., 375/376:406–443, 1987. [doi:10.1515/crll.1987.375-376.406]

[30]   Volker Strassen: The asymptotic spectrum of tensors. J. reine angew. Math., 384:102–152, 1988. [doi:10.1515/crll.1988.384.102]

[31]   Volker Strassen: Degeneration and complexity of bilinear maps: Some asymptotic spectra. J. reine angew. Math., 413:127–180, 1991. [doi:10.1515/crll.1991.413.127]

[32]   Volker Strassen: Algebra and complexity. In First Eur. Congr. Math., Vol. II, volume 120 of Progress Math., pp. 429–446. Birkhäuser, 1994. [doi:10.1007/978-3-0348-9112-7_18]

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

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

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

[36]   Frank Verstraete, Jeroen Dehaene, Bart L. R. De Moor, and Henri Verschelde: Four qubits can be entangled in nine different ways. Phys. Rev. A (3), 65(5):052112, 5, 2002. [doi:10.1103/PhysRevA.65.052112]

[37]   Péter Vrana and Matthias Christandl: Asymptotic entanglement transformation between W and GHZ states. J. Math. Phys., 56(2):022204, 12, 2015. [doi:10.1063/1.4908106]

[38]   Nengkun Yu, Cheng Guo, and Runyao Duan: Obtaining a W state from a Greenberger–Horne–Zeilinger state via stochastic local operations and classical communication with a rate approaching unity. Phys. Rev. Lett., 112(16):160401, 2014. [doi:10.1103/PhysRevLett.112.160401]

[39]   Jeroen Zuiddam: Algebraic complexity, asymptotic spectra and entanglement polytopes. Ph. D. thesis, Univ. Amsterdam, 2018. UvA-DARE.