Back to TGINF

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

Speaker: Josh
Title: Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Date: 30 Sep 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Food: Thai
Audience background:
Talk style:

Abstract: In the first half of the talk, I’ll give an overview of how the state-of-the-art matrix multiplication algorithms are designed. I’ll define a method for designing these algorithms, called the Universal method, which subsumes all the known approaches. Then, in the second half of the talk, I’ll prove new lower bounds on the algorithms one can design by applying the Universal method to many different tensors. The proof will use new tools for upper bounding the asymptotic slice rank of a wide range of tensors. Our main result is that the Universal method applied to any Coppersmith-Winograd tensor (the family of tensors used in all record-holding algorithms from the past 30+ years) cannot yield a bound on omega, the exponent of matrix multiplication, better than 2.16805.

No background knowledge about matrix multiplication algorithms is assumed. Much of the talk is based on joint work with Virginia Vassilevska Williams.