PLEASE NOTE UPDATED LOCATION: JADWIN HALL, ROOM A10
Optimization, Complexity and Math (through the lens of one problem and one algorithm)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.
Avi is a Professor at the School of Mathematics, Institute for Advanced Study, Princeton. I organize the school activities in CSDM (Computer Science and Discrete Mathematics).
His main research interests are:
- Randomness and Computation
- Algorithms and Optimization
- Complexity Theory
- Circuit Complexity
- Proof Complexity
- Quantum Computation and Communication
- Cryptography and Distributed Computation.