Date: November 22, 2018 16:15–17:00
Place: Exactum C122 (Kumpula)
Abstract: We study probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. These probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor $\langle 2,2,2 \rangle$ that represents $2\times 2$ matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank of $\langle 2,2,2 \rangle$ is 7 [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)] we show that the probabilistic rank of $\langle 2,2,2 \rangle$ is at most 6+\frac{6}{7} and the probabilistic border rank is at most 6+\frac{2}{3}. By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs.