Bad and good news for Strassen's laser method: border rank of Perm₃ and strict submultiplicativity

DOI10.1007/S10208-022-09579-3MaRDI QIDQ6142335zbMATH OpenOpenAlexFDO

Authors Austin Conner, Hang Huang, J. M. Landsberg

Publication date 21 December 2023

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.11391

zbMATH Keywords

border rankmatrix multiplication complexitytensor rank

Mathematics Subject Classification ID

Classical groups (algebro-geometric aspects) (14L35) Multilinear algebra, tensor calculus (15A69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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 $3imes3$ 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^{5}otimes{C}^{5}otimes{C}^5$, which could potentially be used to prove $omegaleq2.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.

Cites work

• A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication
• A counterexample to Comon's conjecture
• A method for the solution of certain non-linear problems in least squares
• A note on border rank
• Abelian tensors
• About the maximal rank of 3-tensors over the real and the complex number field
• An Algorithm for Least-Squares Estimation of Nonlinear Parameters
• Apolarity, border rank, and multigraded Hilbert scheme
• Approximate Solutions for the Bilinear Form Computational Problem
• Barriers for fast matrix multiplication from irreversibility
• Barriers for rank methods in arithmetic complexity
• Border rank is not multiplicative under the tensor product
• Cartan for Beginners
• Equations for secant varieties of Veronese and other varieties
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Further limitations of the known approaches for matrix multiplication
• Gaussian elimination is not optimal
• Geometry and complexity theory
• How to multiply matrices faster
• scientific article; zbMATH DE number 727424 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• Limits on the Universal method for matrix multiplication
• Matrix multiplication via arithmetic progressions
• Multigraded Hilbert schemes
• New lower bounds for the border rank of matrix multiplication
• On degeneration of tensors and algebras
• On Grassmann secant extremal varieties
• On the Asymptotic Complexity of Matrix Multiplication
• On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry
• On the nuclear norm and the singular value decomposition of tensors
• On the third secant variety
• Partial and Total Matrix Multiplication
• Polynomials and the exponent of matrix multiplication
• Powers of tensors and fast matrix multiplication
• Product ranks of the 3 3 determinant and permanent
• Rank and border rank of Kronecker powers of tensors and Strassen's laser method
• Rank and optimal computation of generic tensors
• Relative bilinear complexity and matrix multiplication.
• Secant varieties to high degree Veronese reembeddings, catalecticant matrices and smoothable Gorenstein schemes
• Symmetric tensor decomposition
• The bilinear complexity and practical algorithms for matrix multiplication
• The border rank of the multiplication of 2\times 2 matrices is seven
• The Waring rank of the 3 x 3 permanent
• Varieties of sums of power

Cited in

(2)

• Asymptotic spectra: theory, applications, and extensions
• Cartwright-Sturmfels Hilbert schemes

This page was built for publication: Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142335)