Optimization, Complexity and Invariant Theory

Date and location: June 4-8, 2018, Institute for Advanced Study, Princeton, NJ USA

Organizer: Avi Wigderson

Links to the recorded lectures can be found on the Agenda page.

Optimization, Complexity and Invariant Theory Conference


This workshop aimed to explore connections between complexity and optimization with algebra and analysis, which have emerged from the works on operator scaling. The hope was to inform participants from different communities of both basic tools and new developments, and set out new challenges and directions for this exciting interdisciplinary research.

Some of the topics and notions that were included:
Optimization: Alternate minimization. Scaling algorithms. Gradient methods for geodesic convexity. Brascamp-Lieb polytopes. Entropy optimality.
Invariant Theory: Linear group actions, and degree bounds on invariant rings. Nullcone and orbit closure intersection problems. Moment polytopes. Non-commutative duality. Algorithms avoiding Grobner bases.
Computational complexity: Commutative and non-commutative arithmetic circuits. Symbolic matrices. Polynomial identity testing. Tensor rank. Geometric complexity theory.
Quantum Information Theory: Completely positive operators. Quantum distillation. Entanglement polytopes.

Speakers Include:


The workshop was free of charge thanks to the support from the Institute for Advanced Study, Schwab Charitable Fund made possible by the generosity of Eric and Wendy Schmidt, and the Simons Foundation. Please note that attendees registered by May 20, 2018 to attend this free workshop.