YoVDO

Optimization, Complexity and Math - Can We Prove P!=NP by Gradient Descent?

Offered By: Society for Industrial and Applied Mathematics via YouTube

Tags

Complexity Theory Courses Quantum Computing Courses Gradient Descent Courses Invariant Theory Courses

Course Description

Overview

Explore the intersection of optimization, complexity theory, and mathematics in this 55-minute seminar presented by Avi Wigderson from the Institute for Advanced Study. Delve into the intriguing question of whether gradient descent can prove P≠NP. Begin with an introduction to Perfect Matchings (PMs) and their relationship to symbolic matrices, as explored by Edmonds in 1967. Examine the dual life of symbolic matrices and the concept of matrix scaling. Analyze the algorithm for matrix scaling before transitioning to operator scaling, with a focus on Gurvits' 2004 quantum leap in the field. Investigate the operator scaling algorithm and its applications across six different areas and problems, as discussed in GGOW15-16. Explore connections to invariant theory before concluding with open problems and future directions in this fascinating area of applied geometry and algebra.

Syllabus

Intro
Perfect Matchings (PMs)
PMs & symbolic matrices [Edmonds'67]
Symbolic matrices dual life
Matrix Scaling
Analysis of the algorithm
Operator Scaling Gurvits '04 a quantum leap
Operator scaling algorithm
6 areas, 6 problems GGOW15-16
Invariant theory
Conclusions & Open Problems


Taught by

Society for Industrial and Applied Mathematics

Related Courses

Invariant Theory for Computer Scientists
Simons Institute via YouTube
A Recent Perspective on Invariant Theory - Viswambhara Makam
Institute for Advanced Study via YouTube
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing - Yuanzhi Li
Institute for Advanced Study via YouTube
Ideals and Varieties of the Pinhole Camera
Joint Mathematics Meetings via YouTube
Proving Algebraic Identities
Joint Mathematics Meetings via YouTube