Tutorial 4: GCT and Matrix Multiplication
summary
Tutorial lays out concrete GCT tools for tensors: defines border rank and gives explicit criteria using polynomial highest weight vectors to test whether a tensor lies in an orbit closure, translates those criteria into character/partition computations, and shows combinatorial constructions that separate some small tensors from closures. Claims include easily checked vanishing-polynomial witnesses, but also hardness: multiplicity tests become exponential and only partial obstructions are found. Presents worked examples on matrix multiplication tensors, computational experiments, and gaps left for proving nontrivial lower bounds.
AI-written summary · about
chapters (18)
- 0:00Start
- 3:56Tensor rank
- 8:36Complexity of matrix multiplication: the records
- 12:02Border rank ...
- 21:33Representations in rings of regular functions
- 30:54Strassen's resultant for 3-slice tensors
- 33:56Splitting into irreducible representations
- 35:40The idea of comparing multiplicities
- 41:48Occurrence obstructions
- 45:12Decomposition of O(W) and Kronecker coefficients
- 48:59Monoids of representations
- 50:37Coordinate rings of orbits
- 52:06Peter Weyl Theorem
- 53:32Example: generic tensor
- 55:37Example: stabilizer of unit tensor
- 56:56Stability
- 57:43The period of tensors
- 59:32The determinant of tensors
related talks
55mNon-commutative Computation
10mOn the Generality of Matrix Multiplication
53mA Commentary on the Collision of Worlds
20mA Mechanized Algebra of Verified Data Structures for Optimizing Sparse Tensor Programs
21mUniversal High-Performance CFL-Reachability via Matrix Multiplication
24mVerified Tensor-Program Optimization Via High-Level Scheduling Rewrites
01h 01mTrue Complexity of Multilinear Systems
29mApproximating the Permanent of Positive Semidefinite Matrices