Understand
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$.
- Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.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(n^{2.3725})$, and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078})$; in particular, this approach cannot prove the conjecture that for every $\epsilon > 0$, two $n\times n$ matrices can be multiplied in time $O(n^{2+\epsilon})$.
Built on
Gaussian elimination is not optimal
Volker Strassen · 1969
Earlier work this paper cites.
Vermeidung von Divisionen [Avoiding divisions]
Volker Strassen · 1973
Earlier work this paper cites.
Partial and total matrix multiplication
Arnold Schönhage · 1981
Earlier work this paper cites.
Relative bilinear complexity and matrix multiplication
Volker Strassen · 1987
Earlier work this paper cites.
Matrix multiplication via arithmetic progressions
Don Coppersmith and Shmuel Winograd · 1990
Earlier work this paper cites.
Tensor rank is NP-complete
Johan Håstad · 1990
Earlier work this paper cites.
Similar
Algebraic Complexity Theory
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi · 1997
Cited alongside, same era.
A group-theoretic approach to fast matrix multiplication
Henry Cohn and Chris Umans · 2003
Cited alongside, same era.
On the complexity of matrix product
Ran Raz · 2003
Cited alongside, same era.
Group-theoretic algorithms for matrix multiplication
Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans · 2005
Cited alongside, same era.
On the complexity of matrix multiplication
Andrew James Stothers · 2010
Cited alongside, same era.
Then
Breaking the Coppersmith–Winograd barrier
Virginia Vassilevska-Williams · 2012
Later among the works it cites.
Fast matrix multiplication using coherent configurations
Henry Cohn and Chris Umans · 2013
Later among the works it cites.
Improved bound for complexity of matrix multiplication
Alexander Munro Davie and Andrew James Stothers · 2013
Later among the works it cites.
Most tensor problems are NP-hard
Christopher J. Hillar and Lek-Heng Lim · 2013
Later among the works it cites.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…