Скачать или смотреть Border rank lower bounds of the matrix multiplication tensor (Part 1)

Austin Conner (Harvard University)
https://simons.berkeley.edu/talks/aus...
Complexity and Linear Algebra Boot Camp

We continue the discussion of the complexity of matrix multiplication, focusing on the question of lower bounds. In view of the results of Strassen and Bini, in order to understand omega it is enough to understand the rank or the border rank of the matrix multiplication tensor. We will focus our attention on two techniques for border rank lower bounds (and thus also ordinary rank lower bounds) which have been successful when applied to the matrix multiplication tensor: Koszul flattenings and border apolarity. The method of Koszul flattenings associates to a tensor of interest a matrix and relates the rank of the matrix with the rank of the tensor. Border apolarity asserts the existence of a kind of auxiliary data which exists whenever a border rank decomposition exists, and then refutes the existence of this auxiliary data to obtain the nonexistence of a border rank decomposition.

When discussing these methods, the natural symmetry of the problem plays an essential role. For instance, both rank and border rank are invariant under changes of bases in the three tensor factors, so it is not surprising that both techniques are also invariant in their own senses under this symmetry group. Border apolarity, however, goes further, and is only practically applicable in view of the relatively large symmetry group of the matrix multiplication tensor itself, which allows normalization of auxiliary data it wishes to rule out.