Bad and Good News for Strassen's Laser Method: Border Rank of Perm3 and Strict Submultiplicativity.

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. [ABSTRACT FROM AUTHOR]