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.
To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/92482486309. You can also attend in person in DC 1302.
200 University Avenue West
Waterloo, ON N2L 3G1