Bad and good news for Strassen's laser method: Border rank of the 3x3 permanent and strict submultiplicativity
share
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× 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⊗ C^5⊗ C^5, which could potentially be used to prove ω≤ 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 VSP for the small Coppersmith-Winograd tensors.
READ FULL TEXT