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

April 29, 2021
19.00 MSK (UTC +3)
Talk on Big Seminar

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

Avi Wigderson from IAS, Princeton will give the talk "Optimization, Complexity and Math (or, can we prove P ≠ NP using gradient descent)" on the labs' Big Seminar.

The talk will be held in zoom
Meeting ID: 279-059-822 zoom-link
Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.


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 these attempts.
  3. The new algorithms give exponential (or better) improvements in run-time for solving algorithmic many specific problems across CS, Math and Physics. In particular, in algebra (testing rational identities in non-commutative variables), in analysis (testing the feasibility and tightness of Brascamp-Lieb inequalities), in quantum information theory (to the quantum marginals problem), optimization (testing membership in “moment polytopes”), and others. This work exposes old and new connections between these diverse areas.

Based on many joint works in the past 5 years, with Zeyuan Allen-Zhu, Peter Burgisser, Cole Franks, Ankit Garg, Leonid Gurvits, Pavel Hrubes, Yuanzhi Li, Visu Makam, Rafael Oliveira and Michael Walter.

Watch the video:

Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.