MIAO/BARC talk by Robert Andrews
Matrix multiplication and polynomial identity testing
Robert Andrews, University of Illinois Urbana-Champaign
Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that ω, the matrix multiplication exponent, equals 2. If true, this conjecture would yield fast algorithms for a wide array of problems in linear algebra and beyond. But what if ω > 2? In this talk, I will describe how lower bounds on ω can be used to make progress on derandomizing polynomial identity testing.
Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)
More information about upcoming MIAO seminars can be found here
We are hoping to record the seminar and post on the MIAO Research YouTube channel for people who would like to hear the talk but cannot attend.