Matrix multiplication exponent ($C_{15a}$)

• The true value of $\omega$ affects the best possible running time of many other algorithms, including all-pairs shortest paths (APSP), transitive closure, and determinant computation.
• The constant can also be defined in terms of ranks of certain multilinear maps or tensors. Let $U, V, W$ be vector spaces over a field $k$. For a tensor $T \in U \otimes V \otimes W$ define its rank $R(T)$ as the minimal number of summands in the decomposition of $T$ into a sum of elementary tensors. Let $MM_n = \sum_{i,j,k = 1}^n e_{i,j} \otimes e_{j,k} \otimes e_{k, i} \in k^{n \times n} \otimes k^{n \times n} \otimes k^{n \times n}$ be the structure tensor of $n \times n$ matrix multiplication viewed as a bilinear map. Then $\omega = \inf \{ w \mid R(MM_n) = O(n^w) \}$ (see e.g. [B2013]).
• Strictly speaking, the value of $\omega$ may depend on the field over which we consider matrix multiplication. It is known that $\omega$ only depends on the characteristic of the field [S1981]. All known bounds are valid in every characteristic.
• Several surveys, lecture notes, and textbook treatments of the topic at different points of its development are available: [P1984], [G1987], [BCS1997](Chapter 15), [V2012a], [B2013], [LG2017], [L2017](Chapter 3).
• See also: Wikipedia page on matrix multiplication exponent.

References (from the repository page)

• [S1969] Strassen, V. Gaussian elimination is not optimal. Numerische Mathematik 13 (1969), 354–356.
• [P1978] Pan, V. Ya. Strassen's algorithm is not optimal: Trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations. In FOCS 1978, 166–176.
• [P1979] Pan, V. Ya. Field extension and trilinear aggregating, uniting and canceling for the acceleration of matrix multiplication. In FOCS 1979, 28–38.
• [BCRL1979] Bini, D.; Capovani, M.; Romani, F.; Lotti, G. $O(n^{2.7799})$ complexity for $n \times n$ approximate matrix multiplication. Information Processing Lett. 8 (1979), 234–235.
• [B1980] Bini, D. Relations between exact and approximate bilinear algorithms. Applications. Calcolo 17 (1980), 87–97.
• [P1980] Pan, V. Ya. New fast algorithms for matrix operations. SIAM J. Computing 9 (1980), 321–342.
• [S1981] Schönhage, A. Partial and total matrix multiplication. SIAM J. Computing 10 (1981), 434–455.
• [P1981] Pan, V. Ya. New combinations of methods for the acceleration of matrix multiplication. Computers & Mathematics with Applications 7 (1981), 73–125.
• [R1982] Romani, F. Some properties of disjoint sums of tensors related to matrix multiplication. SIAM J. Computing 11 (1982), 263–267.
• [CW1982] Coppersmith, D.; Winograd, S. On the asymptotic complexity of matrix multiplication. SIAM J. Computing 11 (1982), 472–492.
• [P1984] Pan, V. Ya. How to multiply matrices faster. Lecture Notes Comp. Sci. 179, Springer (1984).
• [S1987] Strassen, V. Relative bilinear complexity and matrix multiplication. J. reine angew. Math. 375/376 (1987), 406–443.
• [G1987] de Groote, H. F. Lectures on the complexity of bilinear problems. Lecture Notes Comp. Sci. 245, Springer (1987).
• [CW1990] Coppersmith, D.; Winograd, S. Matrix multiplication via arithmetic progressions. J. Symbolic Computation 9 (1990), 251–280.
• [BCS1997] Bürgisser, P.; Clausen, M.; Shokrollahi, M. A. Algebraic complexity theory. Grundlehren der math. Wiss. 315, Springer (1997).
• [CKSU2005] Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. Group-theoretic algorithms for matrix multiplication. In FOCS 2005, 379–388.
• [S2010] Stothers, A. J. On the complexity of matrix multiplication. PhD thesis, University of Edinburgh (2010).
• [V2012] Vassilevska Williams, V. Multiplying matrices faster than Coppersmith–Winograd. In STOC 2012, 887–898.
• [V2012a] Vassilevska Williams, V. An overview of the recent progress on the exponent of matrix multiplication. SIGACT News 43(4) (2012), 57–59.
• [Z2012] Zhdanovich, D. V. The matrix capacity of a tensor. J. Mathematical Sciences 186 (2012), 599–643.
• [DS2013] Davie, A. M.; Stothers, A. J. Improved bound for complexity of matrix multiplication. Proc. Royal Society of Edinburgh A 143 (2013), 351–369.
• [B2013] Bläser, M. Fast matrix multiplication. Theory of Computing Graduate Surveys 5 (2013), 1–60.
• [V2014] Vassilevska Williams, V. Multiplying matrices in $O(n^{2.373})$ time. Unpublished note (2014), https://theory.stanford.edu/~virgi/matrixmult-f.pdf
• [LG2014] Le Gall, F. Powers of tensors and fast matrix multiplication. In ISSAC 2014, 296–303.
• [LG2017] Le Gall, F. Complexity of matrix multiplication and bilinear problems. Lecture notes for ADFOCS 2017 summer school. https://conferences.mpi-inf.mpg.de/adfocs-17/material/FLG_H1.pdf
• [L2017] Landsberg, J. M. Geometry and complexity theory. Cambridge Studies in Adv. Math. 169, Cambridge University Press (2017).
• [AV2020] Alman, J.; Vassilevska Williams, V. A refined laser method and faster matrix multiplication. TheoretiCS 3 (2024), article 21. Conference paper in SODA 2021, 522–539. arXiv:2010.05846.
• [DWZ2022] Duan, R; Wu, H.; Zhou, R. Faster matrix multiplication via asymmetric hashing. In FOCS 2023, 2129–2138. arXiv:2210.10173.
• [VXXZ2023] Vassilevska Williams, V.; Xu, Y.; Xu, Z.; Zhou, R. New bounds for matrix multiplication: from Alpha to Omega. In SODA 2024, 3792–3835. arXiv:2307.07970.
• [ADVXXZ2024] Alman, J.; Duan, R.; Vassilevska Williams, V.; Xu, Y.; Xu, Z.; Zhou, R. More asymmetry yields faster matrix multiplication. In SODA 2025, 2005–2039. arXiv:2404.16349.
• [DEKMRSZAWB2026] Dupont, E.; Eisenberger, M.; Kozlovskii, B.; Mehrabian, A.; Ruiz, F. J. R.; See, A.; Zhou, R.; Alman, J.; Vassilevska Williams, V.; Balog, M. Improving the matrix multiplication exponent with modern optimization and AlphaEvolve. arXiv:2608.16884.

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 2; best known upper bound 2.371177. Values marked with an asterisk have minimal verification.

Known upper bounds

Known lower bounds