Abstract

A classical result of Strassen connects the exponent $\omega$ of square matrix multiplication to the exponent (asymptotic rank) of the $2\times 2$ matrix multiplication tensor. This talk looks at a collection of recent results that connect exponents of other constant-size tensors to the study of algorithms for a range of hard problems such as the set cover problem, the graph coloring problem, and the matrix permanent problem. We highlight the sequence of balanced tripartitioning tensors as a particular sequence of interest in connection with the matrix permanent problem.

Based on joint work with Andreas Björklund (Lund), Radu Curticapean (Copenhagen & Regensburg), Thore Husfeldt (Copenhagen), Tomohiro Koana (Kyoto), Mateusz Michałek (Konstanz), Jesper Nederlof (Utrecht), and Kevin Pratt (New York).

Video Recording