论文标题
Strassen的激光方法的坏消息：3x3永久和严格的亚皮克性的边界等级
Bad and good news for Strassen's laser method: Border rank of the 3x3 permanent and strict submultiplicativity
论文作者
论文摘要
我们确定了张量的边界等级，这些张量可能会推动矩阵乘法的指数$ω$的已知上限。小$ q = 2 $ coppersmith-Winograd张量等于$ 3 \ times 3 $永久的Kronecker Square，并且有可能用于显示$ω= 2 $。我们证明了复杂性理论的负面结果，即它的边界排名为$ 16 $，解决了一个长期存在的问题。关于它的$ q = 4 $偏斜的表亲，$ c^5 \ otimes c^5 \ otimes c^5 $，有可能用来证明$ω\ leq 2.11 $，我们表明其Kronecker Square的边界排名最多是$ 42 $，这是一个了不起的副本，这是其边境排名$ 64 $ 64 $ 64 $。我们还确定用于小铜匠 - 沃诺格勒张量的Moduli Spaces $ \ usewsuess {vsp} $。
We determine the border ranks of tensors that could potentially advance the known upper bound for the exponent $ω$ of matrix multiplication. The Kronecker square of the small $q=2$ Coppersmith-Winograd tensor equals the $3\times 3$ permanent, and could potentially be used to show $ω=2$. We prove the negative result for complexity theory that its border rank is $16$, resolving a longstanding problem. Regarding its $q=4$ skew cousin in $ C^5\otimes C^5\otimes C^5$, which could potentially be used to prove $ω\leq 2.11$, we show the border rank of its Kronecker square is at most $42$, a remarkable sub-multiplicativity result, as the square of its border rank is $64$. We also determine moduli spaces $\underline{VSP}$ for the small Coppersmith-Winograd tensors.
