Bad and good news for Strassen's laser method: Border rank of the 3x3 permanent and strict submultiplicativity

Abstract

We determine the border ranks of tensors that could potentially advance the known upper bound for the exponent $\omega$ 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 $\omega =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 $\omega \le 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.

References in corpus (1)

• New lower bounds for matrix multiplication and the 3x3 determinant