Kevin Pratt, New York University (NYU)

Abstract

In 1969, Strassen observed that the computational complexity of matrix multiplication is determined by the rank of a particular family of trilinear forms (tensors). This turned out to be a fruitful perspective, which when combined with algebraic and combinatorial tools leads to improvements on the standard cubic-time algorithm. While these improvements have broad applications to algorithm design, algorithmic applications of tensor rank have largely remained in the limited context of matrix multiplication. In this talk I will discuss some other families of tensors whose rank is of algorithmic interest. In particular, I will discuss recent results of Bjorklund, Kaski, and myself, which show that a conjecture of Strassen's would imply that the set cover conjecture is false.

See: https://theory.cs.rutgers.edu/theory_seminar