Algorithmic Applications of Tensor Rank

In this talk, I will discuss the application of tensor rank upper bounds to classic problems in algorithm design. I will first present applications to matrix multiplication and subgraph counting problems, highlighting open problems and the techniques used in these areas. Then, I will discuss the potential application of this algorithmic tool to the set cover problem. I will show that if one could improve certain rank upper bounds even slightly, then an exponential speedup for set cover would follow, thereby refuting a conjecture from fine-grained complexity.