On Matrix Multiplication Algorithms | Richard M. Karp Distinguished Lecture

Fast matrix multiplication is a central goal in algorithms research. Matrix multiplication is a crucial component in many applications, from mathematics and computer science to the sciences, engineering, and even computer games. It is needed whenever a change of coordinates is required, such as in computer graphics, robotics, or physics. It is also central in the solution of linear systems and for many other linear algebraic primitives, such as matrix inverse, determinant, and more, giving applications in many areas, such as machine learning, data analysis, statistical modeling, and more.

The design and analysis of matrix multiplication algorithms has been an active research area for over half a century. In 1969, Strassen introduced the first algorithm for multiplying n by n matrices that outperformed the O(n³) time approach implied by the problem’s definition, achieving a running time of only O(n^{2.81}). Over the decades, faster and faster algorithms were discovered. The goal is to find the smallest real value omega such that n by n matrices can be multiplied in n^{{omega + o(1)}} time in the worst case. Because writing down the n by n output requires at least n² time, we know that omega is at least 2. Whether omega = 2 is possible remains unknown. The current best bound is omega < 2.37134 [ADVXXZ’25].

This talk will broadly discuss the progress on matrix multiplication algorithms over the decades and offer some intuition about where the research area may be headed.

Virginia Vassilevska Williams is a professor at MIT EECS and CSAIL. She obtained her PhD from Carnegie Mellon University in 2008. After research and postdoctoral positions at the Institute for Advanced Study in Princeton, New Jersey, and at UC Berkeley and Stanford, she spent 3.5 years as an assistant professor at Stanford before joining MIT in early 2017. She is the recipient of an NSF CAREER award, a Google Faculty Research Award, a Sloan Research Fellowship, a 2023 Simons Investigator award, and a 2024 FOCS Test of Time Award. In 2018, she gave an invited lecture at the International Congress of Mathematicians.

Refreshments will be served at 3 p.m., before the event.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science and is geared toward a broad scientific audience.

The lecture recording URL will be emailed to registered participants. This URL can be used for immediate access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about five days following each presentation unless otherwise noted.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.