Tata Institute of Fundamental Research
Optimization for Derandomization: Polynomial Identity Testing, Geodesically Convex Optimization and More
STCS Seminar
Speaker:
Ankit Garg (Microsoft Research New England
1 Memorial Dr.
Cambridge, MA 02142
United States of America)
Organiser:
Prahladh Harsha
Date:
Wednesday, 10 Jan 2018, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Ankit Garg (Microsoft Research New England 1 Memorial Dr. Cambridge, MA 02142 United States of America) |
| Organiser: | Prahladh Harsha |
| Date: | Wednesday, 10 Jan 2018, 14:30 to 15:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).