Geometry, representation theory, and the complexity of matrix multiplication

J.M. Landsberg
(Texas A&M University)

Abstract: The naive algorithm for multiplying two n x n matrices uses n3 multiplications. In 1969, in the course of trying to prove the naive algorithm was optimal, Strassen discovered that one can do better (that one needs at most roughly n2.81 multiplications). Just how much better one can do is a central open question in computer science. I will describe how to approach this question via geometry and representation theory, and present recent results.