2020/09/23 by Austin Conner, Conner, Austin, Hang Huang +3
Computer Science · Mathematics · #14L35 #15A69 #68Q15 #Algebraic Geometry (math.AG) #Blind Source Separation Techniques #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2009.11391
openalex publication_date 2020/09/23 · openalex created_date 2020/10/01 · openalex updated_date 2026/07/28
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 C5⊗ C5⊗ C5, 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 \underlineVSP for the small Coppersmith-Winograd tensors.