Approaches to Bounding the Exponent of Matrix Multiplication

on YouTube ↗58m

" summary

Surveys known strategies that upper‑bound omega: handcrafted small tensor ranks and border ranks (Strassen 2.81, Coppersmith–Winograd to 2.38), packing many independent multiplications via the asymptotic sum inequality, and the laser/tensor‑power method yielding diminishing returns (limit ~2.3078 for that family). Proposes embedding n×n multiplication into semisimple algebras (group algebras, then association schemes) using combinatorial conditions like the triple product property and the strong uniquely solvable puzzle conjecture; shows commutative schemes could suffice to reach omega = 2.

AI-written summary · about

" chapters (25)

1. 0:00Start
2. 0:29Introduction
3. 1:21Outline
4. 2:17The matrix multiplication tensor
5. 4:47Upper bounds on rank
6. 14:46"Asymptotic Rank" conjecture CW90
7. 19:27Strong Uniquely Solvable Puzzle
8. 24:04A different approach
9. 25:40The general approach
10. 27:23The Group Algebra
11. 27:52"Nice basis" embedding
12. 28:40The embedding
13. 29:46How many multiplications?
14. 33:09The triangle construction
15. 34:16What should we be aiming for?
16. 36:17Constructions in linear groups
17. 37:54Group algebra approach
18. 39:19General semi-simple algebras
19. 40:21Weighted vs. unweighted MM
20. 44:37Coherent configurations "group theory without groups"
21. 46:54Coherent configs: examples
22. 47:47Adjacency algebra
23. 48:38Nice basis conditions
24. 49:38Coherent configs vs. groups
25. 53:16Open problems