Geometric Complexity Theory and Tensor Rank
summary
Generalizes Strassen’s degree-4 vanishing equations to degree 3k+1 polynomials that vanish on tensors of border rank ≤ 3k, producing a nontrivial lower bound for the border rank of matrix multiplication (with a subtle “−2” adjustment when evaluated). Method uses GL(n)^3 representation theory: restrict to highest-weight vectors built from Young symmetrizers/three-tableau triples, evaluate by a hypergraph chromatic-number argument to prove vanishing, and then check nonvanishing on the matrix multiplication tensor (technical). Also applies to support rank and reproves the 2×2 case border rank 7.
AI-written summary · about
chapters (7)
- 0:00Introduction to GCT
- 5:05Tensors and group action
- 9:38Representation theory basics
- 13:54Highest weight vectors
- 21:10Tableau combinatorics
- 27:26Vanishing and graph theory
- 34:59Conclusion and discussion
related talks
33mOn the Problems Related to Waring Rank and Border Waring Rank
53mThe Geometry of the Identifiability of Tensors
36mThe Rank of Sparse Random Matrices
47mUniqueness of Tensor Decomposition and Identifiability in Mixture Models
51mOptimization On Tensor Network Varieties
59mElementary Results on Maximal, Generic and Typical Ranks
36mOptimizing with Tensors
01h 03mRecent Progress in High-Dimensional Learning