Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Abstract: We study the known techniques for designing Matrix Multiplication (MM) algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method.

We then design a suite of techniques for proving lower bounds on the value of omega, the exponent of MM, which can be achieved by algorithms using many tensors T and the Galactic method. Our main result is that there is a universal constant c > 2 such that a large class of tensors generalizing the Coppersmith-Winograd tensor CW_q cannot be used within the Galactic method to show a bound on omega better than c, for any q.

In this talk, I'll begin by giving a high-level overview of the algorithmic techniques involved in the best known algorithms for MM, and then I'll tell you about our lower bounds. No prior knowledge of MM algorithms will be assumed.

Joint work with Virginia Vassilevska Williams which appeared in FOCS 2018.