Title: Geometry and the complexity of matrix multiplication

 

 

Abstract: In 1968, Strassen discovered a faster way to multiply matrices than the standard row-column multiplication. Since then a fundamental question in theoretical computer science has been to determine just how fast matrices may be multiplied. Strassen's algorithm is at core a certain method to multiply 2 by 2 matrices using 7 multiplications. The data describing this method is equivalently an expression to write the structure tensor of the 2 by 2 matrix algebra as a sum of 7 decomposable tensors. Any such decomposition of an n by n matrix algebra yields a Strassen type algorithm, and Strassen showed that one essentially cannot do better than algorithms coming from such decompositions. Bini later showed all of the above remains true when we allow the decomposition to depend on a parameter and take limits. I discuss a technique for lower bounds for this decomposition problem, border apolarity. Two key ideas to this technique are (i) to not just look at the sequence of decompositions, but the sequence of ideals of the point sets determining the decompositions and (ii) to exploit the symmetry of the tensor of interest to insist that the limiting ideal has an extremely restrictive structure. I discuss its applications to the matrix multiplication tensor and other tensors potentially useful for obtaining upper bounds via Strassen's laser method.