Optimization, Complexity and Math (through the lens of one problem and one algorithm)
Optimization, Complexity and Math (through the lens of one problem and one algorithm)
-
Avi Wigderson, IAS
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.