Alternate Minimization and Scaling Algorithms - Theory, Applications and Connections Across Mathematics and Computer Science

Explore the fascinating intersection of mathematics and computer science in this 52-minute colloquium lecture delivered by Avi Wigderson at the Joint Mathematics Meetings 2018. Delve into the theory, applications, and connections of alternate minimization and scaling algorithms across various disciplines. Gain insights into the P vs NP problem, generalization techniques, and the intricacies of alternate minimization and scaling. Discover the quantum leap in scaling methods, analyze their effectiveness, and understand the role of Gibbs sampling in these algorithms. Examine real-world applications and sources, while gaining a comprehensive understanding of when these algorithms work best.

Introduction
P vs NP
The problem
Generalization
Alternate Minimization
Alternate Scaling
Analysis
Quantum Leap
Scaling
Sources
Recap
When does it work
Gibbs Sampling
Summary