Helsinki Algorithms Seminar: Petteri Kaski, Aalto University "Probabilistic tensors and opportunistic Boolean matrix multiplication"

Probabilistic tensors and opportunistic Boolean matrix multiplication

Petteri Kaski
Aalto University

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. 

Joint work with Matti Karppa (Aalto University).

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.