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.
- 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.
- 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.
- 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.