Bad and good news for Strassen's laser method: Border rank of the 3x3 permanent and strict submultiplicativity
Academic Article
Overview
Research
Additional Document Info
View All
Overview
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 imes 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^5otimes C^5otimes C^5$, which could potentially be used to prove $omegaleq 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.