On the Complexity of Matrix Multiplication and Other Tensors

On the Complexity of Matrix Multiplication and Other Tensors - Joseph Landsberg

Joseph Landsberg
Texas A&M University
November 20, 2012

 

Many problems from complexity theory can be phrased in terms of tensors. I will begin by reviewing basic properties of tensors and discussing several measures of the complexity of a tensor. I'll then focus on the complexity of matrix multiplication. Since March 2012 there have been significant advances in our understanding of the complexity of matrix multiplication. This progress was made possible via tools from algebraic geometry and representation theory, and I'll explain why such techniques are useful without assuming any prior background in them.