Some Lesser-Known Tensors of Algorithmic Interest

Since Strassen’s breakthrough linking the complexity of matrix multiplication to the rank of its associated tensors, tensor rank has been best known in computer science for its role in accelerating matrix multiplication algorithms. Yet recent work has shown that sufficiently strong upper bounds on the ranks of certain other tensors—not just the matrix multiplication tensor—would lead to breakthroughs in algorithm design, resulting in faster algorithms for set cover, computing the permanent of a matrix, and more. In this talk I will tell you about these tensors, why they are useful, and what's known about their ranks. 

This seminar is part of the Problems in Algebraic Geometry Coming from Complexity Theory series.