On the Complexity of Matrix Multiplication and Other Tensors
Presenter
November 20, 2012
Keywords:
- Computer Science and Discrete Mathematics (CSDM)
Abstract
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.