Geometry and the complexity of matrix multiplication

Series
Algebra Seminar
Time
Monday, November 20, 2023 - 1:00pm for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Austin Conner – Harvard University
Organizer
Changxin Ding

Please Note: There will be a pre-seminar (aimed toward grad students and postdocs) from 11 am to 11:30 am in Skiles 006.

Determining the computational complexity of matrix multiplication has been one of the central open problems in theoretical computer science ever since in 1969
Strassen presented an algorithm for multiplication of n by n matrices requiring only O(n^2.81) arithmetic operations. 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 such algorithms are general enough to determine the exponent of matrix multiplication. Bini later showed all of the above remains true when we allow the decomposition to depend on a parameter and take limits.

I present a recent 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 matrix
multiplication tensor 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. This talk discusses joint work with JM Landsberg, Alicia Harper, and Amy Huang.