Approaches to Bounding the Exponent of Matrix Multiplication

on YouTube ↗54m

" summary

Survey of specific progress and a new direction: Strassen’s 2x2 decomposition gives seven multiplications (ω ≤ 2.81), repeated tensor powers and the laser/Coppersmith–Winograd pipeline push ω down to ~2.37, and border rank replaces exact rank in many improvements. A group-algebra reduction uses three subsets with the triple product property to embed k×k multiplication into a group of size ≈k^2, but large character degrees kill the gain. The proposed shift embeds into semi-simple algebras/coherent configurations, defines omega_sub_s (support-rank exponent), and shows omega_sub_s → 2 implies ω → 2.

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 1:58Outline
3. 4:42Tensors
4. 6:23The matrix multiplication tensor
5. 15:52Upper bounds on rank
6. 23:30A different approach
7. 25:13The general approach
8. 28:58The embedding
9. 30:30How many multiplications?
10. 33:00The triangle construction
11. 41:19Group algebra approach
12. 42:17General semi-simple algebras
13. 43:24Weighted vs. unweighted MM
14. 45:54Coherent configurations group theory without groups
15. 46:25Coherent configs vs. groups
16. 47:19Commutative CCs suffice
17. 47:38Open problems