BARC talk by Petteri Kaski

Thursday, 3 October 2019, Petteri Kaski, Associate Professor at Aalto University, will give a talk on "Probabilistic tensors and opportunistic Boolean matrix multiplication".

Title:
Probabilistic tensors and opportunistic Boolean matrix multiplication

Abstract:
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).

Reference:

https://doi.org/10.1137/1.9781611975482.31

Bio

Petteri Kaski is an Assistant Professor in the Department of Computer Science, Aalto University, Helsinki, Finland. His current research interests lie in theory and engineering of exact algorithms for search and enumeration problems, ranging from algebraic techniques for pattern search in graphs to classification problems in combinatorics. He is the recipient of a Kirkman Medal awarded by the Institute of Combinatorics and Its Applications, and a Young Researcher Prize awarded by the Finnish Foundation for Technology Promotion.