Probabilistic tensors and opportunistic Boolean matrix multiplication

Speaker(s)

Petteri Kaski

Affiliation

Department of Computer Science, Aalto University

Date

Nov. 28, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under taking of Kronecker products. Furthermore, the probabilistic extensions enable strictly lower rank over their deterministic counterparts for specific tensors of interest, starting from the tensor <2,2,2> that represents 2-by-2 matrix multiplication. 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 and other subgraphs in graphs. Joint work with Matti Karppa (Aalto University).

---