(Hidden) Symmetries of Computational Problems

on YouTube ↗01h 07m

" summary

Provides a polynomial-time algorithm for the non‑commutative singularity problem by converting it to an operator scaling instance and running an alternating‑minimization (Sinkhorn‑style) routine. Progress uses a capacity potential (an AM‑GM growth argument) and the missing diameter bound is proved via invariant‑theory/representation‑theory degree bounds, so the method actually decides nullcone membership and yields polytime convergence; extensions use geodesic convexity to get faster log(1/ε) rates.

AI-written summary · about

" chapters (12)

1. 0:00Introduction and context
2. 4:16The perfect matching problem
3. 6:33Symbolic matrix singularity
4. 9:22Complexity and implications
5. 14:01Non-commutative singularity
6. 18:13Alternate minimization
7. 24:16Algorithm analysis
8. 29:35Operator scaling
9. 34:41Capacity and convexity
10. 38:40Applications and P vs NP
11. 41:51Invariant theory
12. 51:18Generalization and summary

" related talks

• 01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 40mExponential Lower Bounds on Spectrahedral Representations of Hyperbolicity ConesNick Ryder · Hyperbolic Polynomials and Hyperbolic Programming
• 27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to LearningGeorgina Hall · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 56mEntropy, Capacity, and CountingNisheeth Vishnoi · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 58mContinuous Methods 2Maryam Fazel, Lorenzo Orecchia, Stefanie Jegelka · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 59mCertificates of Polynomial Non-Negativity via Hyperbolic OptimizationJames Saunderson · Hyperbolic Polynomials and Hyperbolic Programming
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 42mTight Semidefinite Programming Relaxations for Polynomial OptimizationJiawang Nie · Hyperbolic Polynomials and Hyperbolic Programming