Optimization, Complexity and Math (through the lens of one problem and one algorithm)

-
Avi Wigderson, IAS
Jadwin Hall A10

I will first introduce and motivate the main characters in this plot:

  • Singularity of symbolic matrices: a basic problem in arithmetic complexity.
  • Alternating Minimization: a basic heuristic in non-convex optimization.

I will then explain how variants of this algorithm are applied to variants of this problem, how these are analyzed, and how the analysis gives rise to problems in and connections between a surprisingly diverse set of mathematical areas. These include  quantum information theory, non-commutative algebra, analysis and invariant theory.  Time permitting, I will discuss challenges this work raises in invariant theory and non-convex optimization. 

No special background will be assumed.