Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication
Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication
复制标题
概率张量和机会布尔矩阵乘法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
P. Kaski
中科院分区：
文献类型：
--
作者：
Matti Karppa;P. Kaski
我们介绍经典的确定性措施的概率扩展的代数复杂性的张量，如秩和边界秩。我们表明，这些概率扩展满足各种自然和算法上的偶然性质，如次乘法下采取克罗内克产品。此外，概率扩展能够改进特定张量的确定性对应物，从表示2 × 2矩阵乘法的张量（cid：104）2，2，2（cid：105）开始。虽然众所周知，（确定性的）张量秩和边界秩满足rk（cid：104）2，2，2（cid：105）= 7和rk（cid：104）2，2，2（cid：105）= 7 [V.斯特拉森，Numer. 13（1969）; J. E. Hopcroft和L. R. Kerr，SIAM J.应用数学20（1971）; S. Winograd，Linear Algebra Appl. 4（1971）; J. M.兰茨贝格，J. AMS 19（2006）]，我们证明了概率张量秩和边界秩满足（cid：101）rk（cid：104）2，2，2（cid：105）≤ 6 + 6 7和（cid：101）rk（cid：104）2，2，2（cid：105）≤ 6 + 2 3 .通过次乘法，这立即导致新的随机算法设计，如布尔矩阵乘法算法以及检测和估计图中三角形的数量。我们的算法是机会主义的
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 (cid:104) 2 , 2 , 2 (cid:105) that represents 2 × 2 matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank satisfy rk (cid:104) 2 , 2 , 2 (cid:105) = 7 and rk (cid:104) 2 , 2 , 2 (cid:105) = 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 (cid:101) rk (cid:104) 2 , 2 , 2 (cid:105) ≤ 6 + 6 7 and (cid:101) rk (cid:104) 2 , 2 , 2 (cid:105) ≤ 6 + 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. Our algorithms are opportunistic in the sense
线性布尔运算符的复杂性
DOI：
10.1561/0400000063
发表时间：
2013
期刊：
Found. Trends Theor. Comput. Sci.
影响因子：
--
作者：
S. Jukna;I. Sergeev
通讯作者：
I. Sergeev