Robert Andrews "On Matrix Multiplication and Polynomial Identity Testing"
Oct 24, 2022 10:00 am
In person 4403 Siebel Center for Computer or Online: https://illinois.zoom.us/j/84700567676?pwd=SG96MlRZT3M0N0paTGFYeEljL2hhUT09
- Sponsor
- Illinois Computer Science
- Speaker
- Robert Andrews, University of Illinois at Urbana-Champaign
- Contact
- Candice Steidinger
- steidin2@illinois.edu
- Phone
- 217-300-8564
- Views
- 111
- Originating Calendar
- Siebel School Speakers Calendar
Join in person at room 4403 or online.
Abstract:
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.