Optimization, Complexity and Math (through the lens of one problem and one algorithm)
Abtract: In this lecture, we introduce and motivate the main characters in this plot:
- Singularity of symbolic matrices: a basic problem in both computational complexity.
- Alternating Minimization: a basic heuristic in non-convex optimization.
I will explain how variants of this algorithm are applied to variants of this problem, how they are analyzed, and how the analysis gives rise to problems in and connections between a surprisingly diverse set of mathematical areas, including quantum information theory, non-commutative algebra and invariant theory, and analysis. Time permitting, we will discuss challenges this work raises in invariant theory and non-convex optimization.
Contact: Bonnie Leung email@example.com