Approaches to Bounding the Exponent of Matrix Multiplication | From the Archive

In this month’s newsletter, we’re highlighting a 2015 talk by Chris Umans on some of the then state-of-the-art approaches to bound the matrix multiplication exponent, an evergreen fundamental topic that will be the focus of one of our upcoming program workshops in October 2025. 

Ten years ago, the Simons Institute hosted a research program on the then-nascent field of Fine-Grained Complexity and Algorithm Design, which aimed to refine the qualitative distinction between computational problems that have relatively efficient solutions and those that are intractable into a quantitative guide to the exact time required to solve problems. This field has since exploded into an expansive subject with many beautiful results and far-reaching connections, thanks in no small part to the impetus provided by the Simons Institute program. Chris Umans’s talk, showcased here, based on joint work with Noga Alon, Henry Cohn, Bobby Kleinberg, Amir Shpilka, and Balázs Szegedy, was delivered as part of one of that program’s workshops.