Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory

on YouTube ↗52m

" summary

Proves that testing membership for 3-tensor slice rank and minrank varieties is NP-hard, and hence orbit closure containment for 3-tensors is NP-hard; extends algebraic natural proofs framework to any family of varieties with NP-hard membership that admits an efficiently generated dense subset, yielding a barrier via generalized algebraic natural proof barrier (succinct hitting sets, PIT used in the argument). Derives several nontrivial equations for the slice-rank and minrank varieties using representation-theoretic GCT techniques, but evaluating those equations on NP-hard instances remains unresolved.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 3:00The Razborov-Rudich barrier
3. 4:44Algebraic natural proofs
4. 9:04Succinct hitting sets
5. 16:09The succinct hitting set barrier (2)
6. 18:35Tensor rank (2)
7. 25:37Variety membership problem
8. 26:45PIT reduces to PIT for constant polynomials
9. 28:16Further ways to specify varieties
10. 30:44Restrictions
11. 37:18Noncommutative identity testing
12. 40:26Valiant's conjecture
13. 41:34Orbit closure containment problem
14. 43:50Properties of varieties
15. 44:35Barriers
16. 46:14Ingredients
17. 47:30Is this the end?

" related talks

• 59mElementary Results on Maximal, Generic and Typical RanksGrigoriy Blekherman · Tensors in Computer Science and Geometry 2014
• 43mGeometric Complexity Theory and Tensor RankChristian Ikenmeyer · Geometric Complexity Theory 2014
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 53mThe Geometry of the Identifiability of TensorsLuca Chiantini · Tensors in Computer Science and Geometry 2014
• 01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 00mOn Approximating the Covering Radius and Finding Dense Lattice SubspacesDaniel Dadush · Lattices: Geometry, Algorithms and Hardness 2020
• 36mOptimizing with TensorsRavi Kannan · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to LearningGeorgina Hall · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)