Computer Science/Discrete Mathematics Seminar I

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.