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 negati...

Full description

Saved in:
Bibliographic Details
Published in:Foundations of computational mathematics 2023, Vol.23 (6), p.2049-2087
Main Authors: Conner, Austin, Huang, Hang, Landsberg, J. M.
Format: Article
Language:English
Subjects:
Applications of Mathematics
Complexity theory
Computer Science
Economics
Linear and Multilinear Algebras
Math Applications in Computer Science
Mathematical analysis
Mathematics
Mathematics and Statistics
Matrix Theory
Numerical Analysis
Tensors
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1615-3375
1615-3383
DOI:10.1007/s10208-022-09579-3