Algorithms that multiply n×n matrices with fewer than n³ arithmetic operations, from Strassen (1969) to the laser method, and their link to tensor rank.
Matrix multiplication is the core operation of dense linear algebra and machine learning; its exponent also governs the best known running times for many graph and optimisation problems.
Multiplying two grids of numbers using fewer steps than the school method, and asking how low the count can go.
1Table multiplication costs n³ steps
2Strassen: 7 products instead of 8
3Tensor rank measures the true cost
4Laser method trims the exponent
5Is the limit exactly 2?
The exponent. Let ω be the smallest number such that two n×n matrices can be multiplied with about nω arithmetic operations. The school method gives . Simply reading the input shows . It is not known whether .
Go deeper
The full technical text.
The exponent
Let ω be the infimum of all τ such that two n×n matrices over a field can be multiplied with O(n arithmetic operations. The schoolbook method gives , and reading the input gives . It is not known whether . The value of can depend only on the characteristic of the field (Schönhage, 1981), so all bounds for hold for every field of characteristic zero.
An AI-generated manuscript dated 2 October 2026 claims ω ≤ 9/4 over ℂ, with a Lean formalisation. Not peer reviewed as of 2026-10-15.
Discussion
ω
≤
3
ω≥2
ω=2
Strassen's trick. In 1969 Strassen showed that two 2×2 block matrices can be multiplied with 7 block multiplications instead of 8. Applied recursively on blocks, the cost is O(nlog27)≈O(n2.807).
The tensor viewpoint. Matrix multiplication can be written as a 3-dimensional array of numbers, a tensor. Its rank is the smallest number of scalar multiplications that suffice in an algorithm of a certain bilinear type. If one can multiply n×n matrices with r multiplications, then ω≤lognr. A more flexible measure, border rank, gives the same exponent. So searching for fast algorithms becomes searching for efficient ways to write a tensor as a sum of simple pieces.
The laser method. Strassen (1986) found how to extract many matrix-multiplication-shaped pieces from the powers of a smaller tensor with nice structure. Coppersmith and Winograd (1987) applied this to a particular tensor and got ω<2.376. Refinements analysing larger powers followed: Stothers (2010) 2.3737, Vassilevska Williams (2012) 2.3729, Le Gall (2014) 2.37287, Alman and Vassilevska Williams (2020) 2.37286, Duan, Wu and Zhou (2022) 2.371866, and further small improvements since (2.371339 in 2024).
Barriers. There are results showing that the laser method applied to certain tensors cannot reach 2, so new ideas may be needed for ω=2.
Why it matters. Many other problems have running times given in terms of ω: solving linear equations, inverting matrices, finding triangles in graphs, and some versions of linear programming. A truly new idea here would ripple across algorithms.
Practice versus theory. The record algorithms have enormous hidden constants and are not used in software. Libraries use the school algorithm tuned for hardware, sometimes with a few levels of Strassen-type recursion for large matrices. Machine search for small algorithms (for particular small sizes) is also active.
Recent preprints push the value slightly lower and are not yet all refereed. Separately, an AI-generated manuscript released in October 2026 claims ω≤9/4 by a non-laser route; it is unrefereed and has not been assessed by experts.
Related: lower bounds. Apart from the trivial n2, the best proven lower bound is about n2logn (Raz), and only in a restricted model (circuits whose constants are bounded). That is far below the n2.37 upper bounds.
τ
)
ω≤3
ω≥2
ω=2
ω
C
Strassen and the tensor viewpoint
In 1969 Strassen showed that two 2×2 block matrices can be multiplied with 7 block multiplications instead of 8. Applied recursively, this gives O(nlog27)≈O(n2.807).
The modern view encodes multiplication of a×b by b×c matrices as a 3-tensor ⟨a,b,c⟩. Its rankR is the minimum number of scalar multiplications in a bilinear algorithm. For square matrices, ω=limn→∞lognR(⟨n,n, and one may replace rank by the more flexible border rank (Bini, 1980). Any bound R(⟨n,n,n⟩)≤r gives ω≤lognr.
The laser method and its descendants
Strassen's laser method (1986–87) extracts large matrix-multiplication tensors from tensor powers of a smaller tensor with nicer structure. Coppersmith and Winograd (1987; journal 1990) applied it to a specific tensor to get ω<2.376. Successive refinements, each analysing higher tensor powers and increasingly careful degenerations, improved the bound:
Stothers (2010): ω<2.3737; Vassilevska Williams (2012): ω<2.3729.
Le Gall (2014): ω<2.37287.
Alman and Vassilevska Williams (2020, SODA 2021): ω<2.37286.
Duan, Wu and Zhou (2022, FOCS 2023): ω<2.371866.
Vassilevska Williams, Xu, Xu and Zhou (2023, SODA 2024): ω<2.371552.
Alman, Duan, Vassilevska Williams, Xu, Xu and Zhou (2024, SODA 2025): ω<2.371339.
Dupont, Alman, Vassilevska Williams, Zhou and colleagues at Google DeepMind (arXiv:2608.16884, 17 August 2026, preprint): ω<2.371177, obtained by solving the optimisation problem at the core of the combination-loss analysis more completely, using modern optimisation methods refined with AlphaEvolve. Version 3 of the 2024 paper (19 August 2026) reports the same bound.
Ambainis, Filmus and Le Gall (2015) and Alman and Vassilevska Williams (2018) proved that broad families of these methods, applied to the Coppersmith–Winograd tensors, cannot reach ω=2.
Practical algorithms
None of the laser-method algorithms is used in practice. They beat the schoolbook method only for astronomically large matrices (they are galactic), have enormous hidden constants, and are numerically less well behaved. Practical fast multiplication means Strassen-like algorithms with small base cases, applied for a few recursion levels before switching to optimised classical kernels. Huang, Smith, Henry and van de Geijn (2016) showed that Strassen's algorithm can be implemented inside the BLIS framework without extra workspace and gives speedups at moderate sizes.
Small formats are therefore still an active search area. AlphaTensor (DeepMind, Nature, October 2022) found algorithms using fewer multiplications for several formats, including 47 multiplications for 4×4 matrices in characteristic 2. AlphaEvolve (2025) found 48 multiplications for 4×4complex matrices, beating the 49 of two-level Strassen. Dumas, Pernet and Sedoglavic (June 2025) gave a 48-multiplication algorithm with rational coefficients, valid over any ring of characteristic other than 2. As a recursion base case this gives exponent log448≈2.7925, versus log449=log27≈2.807.
Where it is used
Beyond dense linear algebra, a smaller ω improves the best known bounds for linear programming (Cohen, Lee and Song, 2018: about nω time up to logarithmic factors with current exponents), triangle detection, several shortest-path problems and, via rectangular matrix multiplication, many fine-grained algorithms.
Claims in October 2026
On 6 October 2026 OpenAI released a repository of AI-generated manuscripts. One (dated 2 October 2026, 13 pages) claims ω≤9/4 over C by a route different from the laser method: it applies Strassen's theory of the asymptotic spectrum of tensors to the tensors of polynomial multiplication. Companion manuscripts claim ω<2.258 over fields of characteristic zero and ω<2.371054886 over every field. OpenAI provides Lean formalisations of the stated bounds. None of this is peer reviewed. The argument also uses a non-constructive existence step, and the claim is about asymptotic arithmetic complexity, not a practical algorithm. See the problem entry.
Dupont et al. improved the numerical optimisation underlying the combination-loss analysis, lowering the best bound to 2.371177. Not yet peer reviewed.
What to read before Fast matrix multiplication (left), and what builds on it: entries that depend on it and the open problems it hosts (right). Every box links to its page.