Papex

Open problem · Computer science · Open

Complexity of matrix multiplication

What is the fastest possible algorithm for multiplying two matrices?

Summary

Algorithms faster than the schoolbook method have been known since Strassen’s in 1969, but the optimal number of operations needed to multiply two n × n matrices is unknown.

AI-assisted claims

Partial result claimed · 06 Oct 2026

An Upper Bound of 9/4 for the Matrix Multiplication Exponent

“We prove that the exponent of matrix multiplication over the complex numbers is at most 9/4.”

By
OpenAI
AI involvement
This repository contains mathematical manuscripts and supporting proof artifacts produced by an internal OpenAI model.
Model
an unreleased internal OpenAI model, as stated
Where
openai/math repository
Formal proof
Lean 4, published by the source
Repository
openai/math at 4eaee87 · read 21 Nov 2026
Source last read
14 Oct 2026

Checks

2 responses

  • 07 Oct 2026 · Response · Scott Aaronson: “Matrix multiplication in n^(9/4+o(1)) time—a rational exponent for once (!), and via a completely different approach than was used for O(n^2.373) and so forth” Source
  • 07 Oct 2026 · Response · Lance Fortnow: “Now these proofs haven't been fully verified but if they hold up, we've seen more progress in theoretical computer science in the last 24 hours than in the previous three decades combined!” Source

Partial result claimed · 17 Aug 2026

Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

“Our combined approach yields an upper bound of ω < 2.371177, improving the previous best bound of 2.371339.”

By
Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog
AI involvement
Second, we leverage recent advances in machine learning to design a new optimization algorithm for this problem. Finally, we refine the resulting optimization algorithm with AlphaEvolve.
Model
AlphaEvolve, as stated
Where
arXiv
Source last read
14 Oct 2026

Claims as their sources state them. Listing a claim is not a check by Papex; the status stays the source’s.

All AI-assisted claims

Why it is open

The schoolbook method computes each of the n² entries of the product as a sum of n products, using n³ multiplications in all [3]. The exponent ω is the smallest real number for which n × n matrices can be multiplied with O(n^(ω+ε)) field operations, for every ε > 0 [7]. The schoolbook method shows that ω ≤ 3, and ω ≥ 2 because any algorithm must output n² entries [7]. The value of ω could in principle depend on the field the entries come from [7].

The open question is where between 2 and 3 the exponent lies; the Wikipedia list asks for "the fastest algorithm for matrix multiplication" [15]. Andris Ambainis, Yuval Filmus and François Le Gall refer to "the conjecture that for every ε > 0, two n × n matrices can be multiplied in time O(n^(2+ε))", that is, that ω = 2 [4]. A resolution would determine ω exactly: either algorithms with O(n^(2+ε)) operations for every ε > 0, which would prove ω = 2, or matching upper and lower bounds at some value above 2.

Lower bounds are far from settling it. Josh Alman and Virginia Vassilevska Williams write that there is "little known in the way of unconditional lower bounds against matrix multiplication" [7]. Ran Raz showed that arithmetic circuits restricted to bounded coefficients need size of order n² log n, and the best lower bounds they report on the rank and the border rank of the matrix multiplication tensor over the complex numbers are 3n² − o(n²) and 2n² − log₂ n − 1 [7]. All of these are of order n² up to a logarithmic factor, so none of them rules out ω = 2 [7].

What is known

Strassen's algorithm (1969). Volker Strassen multiplied 2 × 2 matrices with 7 multiplications instead of 8; applied recursively to blocks, this gives ω ≤ log₂ 7 ≈ 2.81 [1, 3]. In general, a bilinear algorithm that multiplies a k × m by an m × n matrix with r multiplications gives ω ≤ 3 log_(kmn) r, and the least such r is the rank of that format's matrix multiplication tensor [3, 10].

The laser method (1986–2025). Every improvement on ω from 1986 to 2025 came from Strassen's laser method or refinements of it, which analyse large powers of a fixed tensor [3, 7, 9]. Don Coppersmith and Shmuel Winograd's 1990 algorithm ran in time O(n^2.3755); by analysing higher powers of their construction, Andrew Stothers, Vassilevska Williams and Le Gall reached O(n^2.3729) [2, 4], and Le Gall's 2014 bound was ω < 2.37287 [7]. Alman and Vassilevska Williams refined the method and obtained ω < 2.37286 in 2021 [7]. Ran Duan, Hongxun Wu and Renfei Zhou identified a "combination loss" in the analysis of powers of the Coppersmith–Winograd tensor and partly compensated for it, reaching ω < 2.371866 [6]. Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou reached ω ≤ 2.371552, and raised the dual exponent α, the largest α for which an n × n^α matrix can be multiplied by an n^α × n matrix with n^(2+o(1)) operations, to at least 0.321334 [8]. By no longer treating two of the three dimensions identically, Alman, Duan, Vassilevska Williams, Xu, Xu and Zhou obtained ω < 2.371339, published in 2025 [9]. An August 2026 preprint, not peer reviewed, by Emilien Dupont and colleagues, among them Alman, Vassilevska Williams and Zhou, reports ω < 2.371177, found with a new optimisation algorithm refined by AlphaEvolve [11].

Small formats. In 2025 Google DeepMind's AlphaEvolve, a coding agent built on large language models, found a rank-48 algorithm for multiplying two 4 × 4 complex-valued matrices, one fewer than Strassen's algorithm applied recursively, and improved the best known rank for 14 formats; the white paper reports ranks for fixed formats, not a bound on ω [10]. Even the minimum rank for two 3 × 3 matrices is not known [10]; in 2013 it was known to lie between 19 and 23 [3].

Limits of the methods. Ambainis, Filmus and Le Gall showed in 2015 that analysing powers of the Coppersmith–Winograd identity in that way cannot give O(n^2.3725), and that a wide class of variants cannot give O(n^2.3078), so these approaches cannot prove ω = 2 [4]; Duan, Wu and Zhou passed 2.3725 because of a new method for analysing component tensors [6]. Further results show that for many natural families of tensors, even approaches substantially more general than the laser method could not prove ω = 2, although these limits are "very specific to the tensors they are applied to" [7]. For the group-theoretic framework of Henry Cohn and Chris Umans, which reduces matrix multiplication to multiplication in a group algebra, Jonah Blasiak and colleagues ruled out obtaining ω = 2 from abelian groups of bounded exponent [5].

Recent claims. On 6 October 2026 OpenAI released openai/math, a repository of manuscripts "produced by an internal OpenAI model"; one of them, dated 2 October, claims ω ≤ 9/4 over the complex numbers, and two dated 24 September claim ω < 2.258 and α > 0.465 in characteristic zero and ω < 2.371054886006746 over every field [12]. The 9/4 manuscript applies Strassen's spectral theory of tensors to polynomial multiplication, and says that its proof "does not specify a competitive finite matrix size" [12]. The repository lists Lean formalisations of the 9/4 bound, the α bound and the every-field bound, counting additions, subtractions and multiplications in division-free programs; the review status recorded for the whole formalisation catalogue is "unchecked", and no revision of these manuscripts was recorded by 14 October [12]. Scott Aaronson described the 9/4 result as "a rational exponent for once (!), and via a completely different approach than was used for O(n^2.373)" [13], and Gil Kalai called the bound "a substantial advance toward the conjecture ω = 2", noting that the collection's proofs "will need to be checked and digested by the mathematical community" [14]. On 14 October 2026 the Wikipedia list still included the question [15].

Main approaches

The laser method. Bound ω by analysing large tensor powers of a fixed starting tensor, in recent work the Coppersmith–Winograd tensor [4, 7]. Strongest evidence: it produced every improvement on ω from 1986 to 2025 [7, 9], and a 2026 preprint reports a further one [11]. Main difficulty: for the Coppersmith–Winograd family and many other natural tensors these methods cannot reach ω = 2 [4, 7], and each of the last four steps lowered the bound by less than 0.001 [6, 8, 9, 11].

Group-theoretic methods. Reduce matrix multiplication to multiplication in the group algebra of a suitable finite group [5]. Strongest evidence: the known laser-method techniques can be simulated within this framework [7], and Cohn, Robert Kleinberg, Balázs Szegedy and Umans formulated conjectures that would give ω = 2 [5]. Main difficulty: abelian groups of bounded exponent cannot give ω = 2; the journal's summary of that result notes that abelian groups of unbounded exponent and non-abelian groups remain possible [5].

Computer search for small formats. Search directly for low-rank decompositions of small matrix-multiplication tensors, with alternating least squares, deep reinforcement learning, custom search or AI coding agents [10]. Strongest evidence: a rank-48 algorithm for 4 × 4 complex matrices and improvements in 14 formats [10]. Main difficulty: a fixed format gives only ω ≤ 3 log_(kmn) r [3], which for 4 × 4 matrices with rank 48 is about 2.79, and even the 3 × 3 rank is unknown [10].

Lower bounds. Prove that matrix multiplication needs more than about n² operations, in restricted models or through tensor rank [7]. Strongest evidence: the n² log n bound for bounded-coefficient circuits and the rank and border-rank bounds above [7]. Main difficulty: none of these bounds moves the lower bound on ω above 2 [7].

Open sub-questions

  1. Checking the 9/4 argument. Do the separation construction and the growth estimate for polynomial multiplication in the 9/4 manuscript hold as written, and does its Lean statement say the same as the manuscript's main theorem [12]?
  2. The 3 × 3 rank. What is the rank of 3 × 3 matrix multiplication? It lay between 19 and 23 in 2013 [3] and was still unknown in 2025 [10]; a rank of 21 would already improve on Strassen's exponent [3].
  3. Beyond n² lower bounds. Can the rank or border rank of the n × n matrix multiplication tensor be shown to exceed 3n², or to grow faster than any constant times n² [7]? Explicit tensors of high rank are also a target on the Papex page P versus NP.
  4. Non-abelian groups. Can non-abelian groups, or abelian groups of unbounded exponent, which the cap-set bounds do not exclude, give ω = 2 in the group-theoretic framework [5]?
  5. Dependence on the field. Does ω depend on the field [7]? The 2026 manuscripts claim a different bound over the complex numbers from the one over every field, including those of positive characteristic [12].

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Strassen, V. (1969). Gaussian elimination is not optimal. Numerische Mathematik 13(4), 354–356. 10.1007/BF02165411 · Checked 14 Oct 2026
  2. Coppersmith, D. & Winograd, S. (1990). Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation 9(3), 251–280. 10.1016/S0747-7171(08)80013-2 · Checked 14 Oct 2026
  3. Bläser, M. (2013). Fast matrix multiplication. Theory of Computing Library, Graduate Surveys 5, 1–60. 10.4086/toc.gs.2013.005 · Checked 14 Oct 2026
  4. Ambainis, A., Filmus, Y. & Le Gall, F. (2015). Fast matrix multiplication: limitations of the Coppersmith–Winograd method. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC '15), 585–593. 10.1145/2746539.2746554 · Checked 14 Oct 2026
  5. Blasiak, J., Church, T., Cohn, H., Grochow, J. A., Naslund, E., Sawin, W. F. & Umans, C. (2017). On cap sets and the group-theoretic approach to matrix multiplication. Discrete Analysis 2017:3. 10.19086/da.1245 · Checked 14 Oct 2026
  6. Duan, R., Wu, H. & Zhou, R. (2023). Faster matrix multiplication via asymmetric hashing. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2129–2138. 10.1109/FOCS57990.2023.00130 · Checked 14 Oct 2026
  7. Alman, J. & Vassilevska Williams, V. (2024). A refined laser method and faster matrix multiplication. TheoretiCS 3, Article 21, 1–32. Conference version in SODA 2021, 522–539. 10.46298/theoretics.24.21 · Checked 14 Oct 2026
  8. Vassilevska Williams, V., Xu, Y., Xu, Z. & Zhou, R. (2024). New bounds for matrix multiplication: from alpha to omega. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 3792–3835. 10.1137/1.9781611977912.134 · Checked 14 Oct 2026
  9. Alman, J., Duan, R., Vassilevska Williams, V., Xu, Y., Xu, Z. & Zhou, R. (2025). More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005–2039. 10.1137/1.9781611978322.63 · Checked 14 Oct 2026
  10. Novikov, A., Vũ, N., Eisenberger, M., Dupont, E., Huang, P.-S., Wagner, A. Z. et al. (2025). AlphaEvolve: a coding agent for scientific and algorithmic discovery. Google DeepMind white paper, arXiv preprint 2506.13131. Source · Checked 14 Oct 2026
  11. Dupont, E., Eisenberger, M., Kozlovskii, B., Mehrabian, A., Ruiz, F. J. R., See, A., Zhou, R., Alman, J., Vassilevska Williams, V. & Balog, M. (2026). Improving the matrix multiplication exponent with modern optimization and AlphaEvolve. arXiv preprint 2608.16884 (17 August 2026). Source · Checked 14 Oct 2026
  12. OpenAI (2026). An Upper Bound of 9/4 for the Matrix Multiplication Exponent. OpenAI Math Release preprint, manuscript dated 2 October 2026, released 6 October 2026, with the other manuscripts of result family 107. Source · Checked 14 Oct 2026
  13. Aaronson, S. (2026). The Mathocalypse. Shtetl-Optimized, 7 October 2026 (updated 9 and 12 October). Source · Checked 14 Oct 2026
  14. Kalai, G. (2026). Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans. Combinatorics and more, 7 October 2026. Source · Checked 14 Oct 2026
  15. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 14 Oct 2026

Page reviewed 14 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 29 Sep 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing