Border apolarity of tensors and the complexity of matrix multiplication

HARVARD-MIT ALGEBRAIC GEOMETRY

Speaker:

Austin Conner - Harvard University

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. I will briefly discuss this problem and its reduction to deciding on which secant variety to the Segre embedding of a product of three projective spaces the matrix multiplication tensor lies. I will explain a recent technique to rule out membership of a fixed tensor in such secant varieties, border apolarity. Border apolarity establishes the existence of certain multigraded ideals implied by membership in a particular secant variety. These ideals may be assumed to be fixed under a Borel subgroup of the group of symmetries of the tensor, and in the simplest case, can consequently be tractably shown not to exist. When ideals exist satisfying the easily checkable properties, one must decide if they are limits of ideals of distinct points on the Segre. This talk discusses joint work with JM Landsberg, Alicia Harper, and Amy Huang.

Zoom: https://harvard.zoom.us/j/91794282895?pwd=VFZxRWdDQ0VNT0hsVTllR0JCQytoZz09