Algebra provides a powerful set of tools to solve problems throughout computer science. Basic tasks such as matrix multiplication, polynomial arithmetic, and solving linear equations have wide-ranging applications, yet many fundamental questions about computational algebra remain unanswered. Can matrices be multiplied as quickly as they can be added? Can algebraic algorithms be derandomized efficiently? How expensive is it to solve a system of polynomial equations?
Robert Andrews,
University of Waterloo
In this talk, I will present my work on the power and limitations of algebraic algorithms. I will illustrate how algebraic identities lead to surprisingly efficient algorithms, and how provably hard problems can be used to reduce the use of randomness in computational algebra.
Robert Andrews is a William T. Tutte Postdoctoral Fellow at the University of Waterloo. Previously, he was a postdoctoral researcher at the Institute for Advanced Study and the Simons Institute for the Theory of Computing. He received his Ph.D. from the University of Illinois Urbana-Champaign in 2023, advised by Michael A. Forbes. His research interests include complexity theory, pseudorandomness, and computational algebra. His work has been recognized with the Machtey Award for Best Student Paper at FOCS 2022.