TCS+ Talk

Wednesday January 31, 2018 10:00 AM

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

Speaker: Avi Wigderson, Princeton University
Location: Annenberg 205

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.

Series TCS+ Talks

Contact: Bonnie Leung