Revised: July 19, 2020

Published: September 3, 2021

**Keywords:**matrix multiplication, algebraic complexity

**Categories:**complexity theory, lower bounds, algebraic complexity, matrix multiplication, CCC, CCC 2019 special issue

**ACM Classification:**F.2.2

**AMS Classification:**68Q17

**Abstract:**
[Plain Text Version]

We prove limitations on the known methods for designing matrix multiplication algorithms. Alman and Vassilevska Williams (FOCS'18) recently defined
the *Universal Method*, which
generalizes all the known approaches,
including Strassen's Laser Method (J. reine angew. Math., 1987) and
Cohn and Umans's Group Theoretic Method (FOCS'03). We prove concrete
lower bounds on the algorithms one can design by applying the Universal Method
to many different tensors. Our proofs use new tools to give upper bounds on
the *asymptotic slice rank* of a wide range of tensors. Our main result is that the Universal Method applied to any Coppersmith--Winograd tensor $CW_q$ cannot yield a bound on $\omega$, the exponent of matrix multiplication, better than $2.16805$.
It was previously known (Alman and Vassilevska Williams, FOCS'18)
that the weaker “Galactic Method” applied to $CW_q$ could
not achieve an exponent of $2$.

We also study the Laser Method (which is a special case of the
Universal Method) and prove that it is
“complete” for matrix multiplication algorithms: when it applies to a tensor $T$, it achieves $\omega = 2$ if and only if it is possible for the Universal Method applied to $T$ to achieve $\omega = 2$. Hence, the Laser Method, which was originally used as an algorithmic tool, can also be seen as a
lower-bound tool for a large class of algorithms.
For example, in their landmark paper, Coppersmith and Winograd
(J. Symbolic Computation, 1990)
achieved a bound of $\omega \leq 2.376$, by applying the Laser Method to $CW_q$. By our result, the fact that they did not achieve $\omega=2$ *implies* a lower bound on the Universal Method applied to $CW_q$.

-----

A conference version of this paper appeared in the 34th Computational Complexity Conference, 2019.

Supported in part by NSF grants CCF-1651838 and CCF-1741615. The work reported here was done while the author was a Ph.D. student at MIT.