JM Landsburg: Geometry and the Complexity of Matrix Multiplication

In 1969 Strassen discovered the standard algorithm for multiplying nxn matrices, that takes O(n^3) arithmetic operations, is not the best. Since then, after considerable research, it is generally conjectured in the computer science community that as n goes to infinity, it becomes nearly as easy to multiply matrices as it is to add them (i.e., that O(n^{2+epsilon}) arithmetic operations is possible). I will survey the contributions of geometry to this problem, namely lower complexity bounds obtained by finding polynomials that distinguish between the set S of bilinear maps that can be computed with a small number of arithmetic operations from the bilinear map corresponding to matrix multiplication. The polynomials are found by exploiting the symmetries of the set S and using general results from algebraic geometry. I will also discuss very recent work indicating that geometry may also have a role to play in determining upper bounds and finding algorithms.