Proving Asymptotic Upper Bounds for Matrix Multiplication - Part 1

Learn the fundamental concepts and tools of the laser method for proving asymptotic upper bounds on matrix multiplication exponents in this lecture from the Complexity and Linear Algebra Boot Camp. Explore the groundbreaking techniques invented by Strassen and Coppersmith-Winograd in 1987, covering essential topics including tensor rank and restriction, border rank and degeneration, asymptotic sum inequality, and tight sets. Delve into the mathematical foundations that underpin modern approaches to understanding the computational complexity of matrix multiplication, with detailed explanations drawn from Chapter 15 of algebraic complexity theory.