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

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.

author list (cited authors)

  • Conner, A., Huang, H., & Landsberg, J. M.

publication date

  • January 1, 2020 11:11 AM