- Algebra Seminar
- Monday, November 20, 2023 - 1:00pm for 1 hour (actually 50 minutes)
- Skiles 006
- Austin Conner – Harvard University
- 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.
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.