Matrix Multiplication

on YouTube ↗01h 44m

" summary

Asks how fast N×N multiplication can be done and connects concrete algebraic claims to algorithms: uses rank vs border rank (Strassen shows 2×2 rank ≤7; a bordering construction gives border rank 5) to turn small-tensor bounds into exponent ω bounds via Schönhage’s decomposition and tensor powering; analyzes the Kupferman–Winograd family (CW tensor (border rank q+2)) and its limiting “value” method (explains why that framework cannot reach ω=2); notes an alternative group‑theoretic embedding that reproduces ω≈2.376.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 0:32Matrix multiplication basics
3. 2:23Straight-line programs
4. 5:50Complexity measures
5. 8:07Bilinear algorithms
6. 12:50Rank and recursion
7. 19:28Tensors and notation
8. 28:43Tensor operations
9. 33:54Permutation invariance
10. 37:40Border rank introduction
11. 42:46Defining border rank
12. 49:48Proving complexity bounds
13. 57:43Tensor restrictions
14. 1:11:38Coppersmith-Winograd
15. 1:30:14Group theoretic approach