Seminar • Algorithms and Complexity • On Matrix Multiplication and Polynomial Identity Testing

Please note: This seminar will take place in DC 1302 and online.

Robert Andrews, PhD candidate
Department of Computer Science, 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. If instead ω > 2, can we leverage the hardness of matrix multiplication to design algorithms for other problems? In this talk, I will describe how lower bounds on ω can be used to make progress on derandomizing polynomial identity testing.