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 improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor h2, 2, 2i that represents 2 × 2 matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank satisfy rk h2, 2, 2i = 7 and rk h2, 2, 2i = 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 tensor rank and border rank satisfy rk e h2, 2, 2i ≤ 6 + 67 and rk e h2, 2, 2i ≤ 6 + 23 . 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. Our algorithms are opportunistic in the sense that their worst-case scaling is essentially governed by the probabilistic rank, yet their result is accumulated through independent repetitions, where the partial result can be inspected at each repeat for possible early termination, and each repeat scales according to the rank of the outcome-tensors. For example, representing h2, 2, 2i probabilistically using an ensemble of tensors of rank 6, we obtain an algorithm that, with high probability, multiplies two 2d × 2d Boolean matrices in Õ((6 + 67 )d) operations. This algorithm consists of independent repeats that each run in O(6d) operations and enable inspection of the partial result at each repeat. Analogously, a probabilistic representation of h2, 2, 2i using tensors of border rank 5 gives an algorithm that runs in Õ((6 + 23 )d) operations, consisting of repeats that run in Õ(5d) operations each. Asymptotically, we use Adleman’s argument to show that, over the complex field, the support rank exponent ωs of matrix multiplication [H. Cohn and C. Umans, SODA’12] gives the lower bound ωs ≤ inf τ : rk e ht, t, ti = O(tτ ) for probabilistic tensor rank. While this enables an approach to obtaining asymptotically faster algorithm designs for matrix multiplication via the Cohn-Umans inequality ω ≤ 32 ωs − 1, the main motivation for the present paper is to enable an approach towards fast practical algorithms using small probabilistic tensors.