Avi Wigderson “Optimization, Complexity and Math (or, can we prove P ≠ NP using gradient descent)“

It is our pleasure to share the Big Seminar talk “Optimization, Complexity and Math (or, can we prove P ≠ NP using gradient descent)“ by Avi Wigderson. Abstract: This talk aims to summarize the status and goals of a broad research project. The main messages of this project are summarized below; I plan to describe, through examples, many of the concepts they refer to, and the evolution of ideas leading to them. No special background is assumed. (1) We extend some basic algorithms of convex optimization from Euclidean space to the far more general setting of Riemannian manifolds, capturing the symmetries of non-commutative group actions. The main tools for analyzing these algorithms combine central results from invariant and representation theory. (2) One main motivation for studying these problems and algorithms comes from algebraic complexity theory, especially attempts to separate Valiant’s algebraic analogs of the P and NP. Symmetries and group actions play a key role in the