PACM Colloquium: Avi Wigderson, Institute for Advanced Study

Mon, Apr 8, 2019, 4:00 pm


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.
Jadwin A10
Event category: 

Upcoming Events

ANALYSIS OF FLUIDS AND RELATED TOPICS: Turbulent solutions of fluid equations: Alexey Cheskidov, University of Illinois at Chicago

PACM Colloquium, Prof. Lin Lin, UC Berkeley University

Mon, Feb 6, 2023, 4:30 pm
Location: 214 Fine Hall

ANALYSIS OF FLUIDS AND RELATED TOPICS: Kevin Zumbrun, Indiana University

Thu, Feb 9, 2023, 3:00 pm
Location: Fine Hall 314