Optimization for Derandomization: Polynomial Identity Testing, Geodesically Convex Optimization and More

Randomness plays an important role across scientific disciplines. In theoretical computer science, there is a large body of work trying to understand the role of randomness in computation. An important part in this quest is the polynomial identity testing question which asks if one can test identities deterministically. In this talk, I will talk about deterministic identity testing of a special class of polynomials using tools from optimization such as alternating minimization and second order methods. The class of problems that we solve form an amazing web of connections across areas such as geodesically convex optimization, quantum information theory, representation theory, non-commutative algebra and functional analysis. I will also outline applications to these areas (the talk will be based on several joint works with Zeyuan Allen-Zhu, Peter Burgisser, Leonid Gurvits, Yuanzhi Li, Rafael Oliveira, Michael Walter and Avi Wigderson).