Matrix multiplication via matrix groups
summary
Paper proves in the Cohn–Umans group-theoretic framework that groups of Lie type cannot yield omega = 2, by combining Gowers’s quasirandomness bounds (PSL(2, Fp) gives I(G) ≤ |G|^{8/9}) with the triple-product/product-free-triple obstruction to embed large matrix multiplication tensors — this rules out beating about 2.25 and in some cases pushes the bound back toward 3. The paper also defines a continuous “Lie exponent,” constructs submanifolds in SL(n,R)^m with the triple product property, and shows Lie exponent approaches 3 for large powers of SL(n,R) while leaving open whether matrix groups can ever achieve omega = 2.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:18The exponent of matrix multiplication
- 1:29A group-theoretic approach [CU03] Let G be a finite group
- 4:53Prior work
- 7:35Barriers for groups of Lie type
- 8:08Quasirandom groups
- 11:16Proof of our Theorem for PSL(2, F,)
- 14:31The general case
- 16:07A continuous setting
- 21:08Open questions
related talks
01h 02mFine-Grained Counting Complexity I
01h 01mComplexity and Algorithmic Game Theory I
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 04mThe challenge of managing parallelism and data-movement for tensor computations on GPUs
31mPrivacy-preserving decentralized memory for federated learning (aka secure MPC)
58mLower Bound Issues in Computational Social Choice
19mComputing Cohomology Rings in Cubical Agda
26mRapunSL: Untangling Quantum Computing with Separation, Linear Combination and Mixing