# Fast Matrix Multiplication: Limitations of the Laser Method

arXiv: https://arxiv.org/abs/1411.5414 · HTML: https://mlsanity.com/paper/1411.5414/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2014.

## Built on by (most cited first, 2 of 2)

- [Triplet Interaction Improves Graph Transformers: Accurate Molecular Graph Learning with Triplet Graph Transformers](https://mlsanity.com/paper/2402.04538/) (2024)
- [Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles](https://mlsanity.com/paper/2301.00074/) (2022)

## Abstract (arXiv)

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time O(n2.3078); in particular, this approach cannot prove the conjecture that for every ε > 0, two n× n matrices can be multiplied in time O(n2+ε). We describe a new framework extending the original laser method, which is the method underlying the previously mentioned algorithms. Our framework accommodates the algorithms by Coppersmith and Winograd, Stothers, Vassilevska-Williams and Le Gall. We obtain our main result by analyzing this framework. The framework is also the first to explain why taking tensor powers of the Coppersmith-Winograd identity results in faster algorithms.