Computer Science/Discrete Mathematics Seminar I

On Matrix Multiplication and Polynomial Identity Testing

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that matrices can be multiplied in nearly-linear time. If true, this conjecture would yield similarly-fast algorithms for a wide array of problems in linear algebra and beyond. However, if such near-linear time algorithms for matrix multiplication do not exist, is it possible to leverage the hardness of multiplying matrices to design algorithms for other problems? In this talk, I will describe how lower bounds on the complexity of matrix multiplication can be used to design a faster deterministic algorithm to test if two polynomials, encoded as algebraic circuits, are equal.

Date & Time

January 30, 2023 | 11:15am – 12:15pm

Location

Simonyi 101 and Remote Access

Speakers

Robert Andrews

Speaker Affiliation

University of Illinois Urbana-Champaign