Colloquium Details
Algorithms and Barriers for Fast Matrix Multiplication
Speaker: Josh Alman, Harvard University
Location: Online
Date: March 30, 2021, 11:30 a.m.
Host: Oded Regev
Synopsis:
Matrix multiplication is one of the most basic algebraic operations. Since Strassen's surprising breakthrough algorithm from 1969, which showed that matrices can be multiplied faster than the most straightforward algorithm, algorithmic problems from nearly every area of computer science have been sped up by clever reductions to matrix multiplication. It is popularly conjectured that two n × n matrices can be multiplied in roughly O(n^2) time, but we don't yet have the algorithmic techniques needed to achieve this.
In this talk, I'll give an overview of my work on this important problem, in the broad context of my research on combining ideas from algorithm design and complexity theory to understand problems throughout computer science. First, I'll give an overview of known applications of matrix multiplication, including some new applications to nearest neighbor search and processing data streams. Second, I'll talk about the fastest known algorithm for matrix multiplication, which runs in time O(n^2.37286), which I recently designed with Virginia Vassilevska Williams. Third, I'll describe new barrier results which help to explain why we've been stuck for so long on this problem, and describe what kinds of insights are needed for further improvements.
Speaker Bio:
Josh Alman is a Michael O. Rabin postdoctoral fellow in theoretical computer science at Harvard University. He earned his Ph.D. in computer science from MIT in 2019, where he was advised by Virginia Vassilevska Williams and Ryan Williams. He works on both algorithm design and complexity theory, and much of his work combines tools and insights from both areas. He's particularly interested in developing algebraic tools like algorithms for matrix multiplication and Fourier transforms, and applying them to problems throughout computer science. His awards include the European Association of TCS Distinguished Dissertation Award, the George M. Sprowls Award for outstanding Ph.D. theses in computer science at MIT, and best student paper awards at CCC 2019 and FOCS 2019.