Wednesday, May 5, 2021 - 3:00pm to 4:00pm
Event Calendar Category
Uncategorized
Speaker Name
Josh Alman
Affiliation
Harvard
Join Zoom meeting
https://mit.zoom.us/j/97637459251
Abstract
The complexity of matrix multiplication is measured in terms of ω, the smallest real number such that two n×n matrices can be multiplied using O(n^{ω+ϵ}) field operations for all ϵ>0; the best bound until now is ω<2.37287 [Le Gall'14]. All bounds on ω since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on ω, and we indeed obtain the best bound on ω to date: ω<2.37286. The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity. In this talk, I'll give an overview of how the laser method works and our new improvement. No background about matrix multiplication algorithms will be assumed. Joint work with Virginia Vassilevska Williams.
Biography
Josh Alman is a Rabin Postdoc in the Theoretical Computer Science at Harvard University. He works on algorithm design and complexity theory, which includes using algebraic tools to solve problems throughout computer science. He completed his PhD in Computer Science at MIT, advised by Ryan Williams and Virginia Vassilevska Williams. He spent the first half of grad school at Stanford until he moved to MIT with his advisors.