Matrix multiplication exponent: is ω = 2, i.e. n^(2+o(1)) operations for n×n products?
Difficulty 82: fifty years of tiny laser-method gains, barrier theorems against the dominant method, and no known route to 2; the unrefereed, non-constructive 9/4 claim would be a striking new method but would not reach 2, so it barely moves the number. Ranked above strongly polynomial LP (77) and below classical factoring (84). Application value 31: the asymptotic algorithms are galactic, so the benefit comes from spin-off small-format algorithms and cleaner bounds, slightly above RH (30). Leverage 72: running times across linear algebra, graph algorithms and fine-grained complexity are stated in terms of ω, close to abc (74).
The problem
Can two n-by-n tables of numbers be multiplied in close to n² steps, the bare minimum, instead of n³?
- 1School method costs n³ steps
- 2Strassen: fewer multiplications
- 3Laser method trims the exponent
- 4Best now a bit above 2.37
- 5Is the true limit exactly 2?
Definition. Let be the infimum of such that matrices over the complex numbers can be multiplied with arithmetic operations. Trivially . The question: is ? Equivalently, is the tensor rank of matrix multiplication ? The answer can depend only on the characteristic of the field.
Built from
earlier problems → this oneThe problems this one is built from: progress or tools it needs (builds on), special cases that come first (generalizes), and weaker results on the way (implies). On the right, what builds on it.
- Start with
- Cap sets in 𝔽₃ⁿ: the growth constant, between 2.2202 and 2.7552Combinatorics · D58
- Step 2
- Matrix multiplication exponent: is ω = 2, i.e. n^(2+o(1)) operations for n×n products?This problem
- Then
- APSP and 3SUM hypotheses: no n^(3−ε) APSP or n^(2−ε) 3SUM on polynomially bounded integersComplexity Theory · D32
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Fast matrix multiplicationAlgorithm · host
- Then
- Matrix multiplication exponent: is ω = 2, i.e. n^(2+o(1)) operations for n×n products?The problem
State of the art
Accepted upper bounds (laser method): (Stothers, 2010), (Vassilevska Williams, 2012), (Le Gall, 2014), (Alman and Vassilevska Williams, 2020), (Duan, Wu, Zhou, 2022), (Vassilevska Williams, Xu, Xu, Zhou, 2023) and (Alman et al., arXiv April 2024, SODA 2025). Preprints of 17 and 19 August 2026 (Dupont et al., arXiv:2608.16884, and version 3 of the 2024 paper) report ; these follow established methods and are by the leading groups, but are not yet refereed.
Realistic applications
The asymptotically fast algorithms are galactic (astronomical constants, poor numerical behaviour) and have little direct practical value; practical fast multiplication uses Strassen-like schemes with small base cases. Proving , or any large improvement such as , would improve theoretical exponents for linear programming (via interior-point methods), triangle finding, shortest-path-type problems and linear-algebra primitives. The methods that matter in practice are small-format tensor decompositions (e.g. the 48-multiplication algorithms), used as recursion base cases in numerical libraries.
What counts as solved
A proof, accepted by experts, that (algorithms for every ), or an unconditional lower bound showing (beyond current techniques). For the October 2026 claim of to count as established progress, experts must verify the manuscript and confirm that the Lean statement matches the standard definition of .
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
No Lean statement of ω exists: neither Mathlib nor Formal Conjectures (Formal Conjectures pinned at commit e754a78 (17 October 2026)) defines the matrix multiplication exponent. The corpus file Arxiv/0805.3777/TensorRank.lean defines the CP rank of tensors (Holor.cprank), the ingredient ω is built from, but states no bound on ω. An upper-bound improvement comes as an explicit tensor (or algorithm) construction plus an asymptotic analysis such as the laser method; the finite construction can be checked exactly by computer, while the asymptotic argument is refereed. Once ω is stated in Lean (as the infimum of τ with rank ⟨n,n,n⟩ = O(n^τ)), this moves to LEAN.
Claims under verification
+ add a claimWhere the work is
Reaching ω = 2 needs methods beyond the laser method; current gains come from heavy computational optimization of laser analyses. Verifying the claimed 9/4 bound is the immediate theoretical task.
Bottlenecks
ranked by votes- #1TheoryLaser-method barriers
Ambainis–Filmus–Le Gall (2015) and Alman–Vassilevska Williams (2018) proved that broad classes of laser-method analyses of Coppersmith–Winograd-type tensors cannot reach . Accepted gains since 2010 total about 0.002, so a different starting tensor or method is required.
severity
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Oct 6, 2026OpenAI release claims ω ≤ 9/4 (unrefereed)source
OpenAI released an AI-generated manuscript dated 2 October 2026 and a Lean formalisation claiming ω ≤ 9/4 over ℂ. Not peer reviewed as of 2026-10-15.
- Aug 17, 2026ω < 2.371177 (preprint)source
Dupont et al. lowered the bound via a reformulated optimisation problem refined with AlphaEvolve. Not yet refereed.
- Apr 25, 2024ω < 2.371339source
Alman, Duan, Vassilevska Williams, Xu, Xu and Zhou added asymmetry to the combination-loss analysis (first versions; SODA 2025).
- Oct 18, 2022ω < 2.371866source
Duan, Wu and Zhou introduced asymmetric hashing, improving on 2.37286.