A 2n^2-_2(n)-1 lower bound for the border rank of matrix multiplication

DOI10.1093/IMRN/RNX025MaRDI QIDQ4619419zbMATH OpenOpenAlexFDO

Authors Mateusz Michalek, J. M. Landsberg

Publication date 6 February 2019

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

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

zbMATH Keywords

border rankmatrix multiplication complexity

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: Let M_n denote the matrix multiplication tensor for nxn matrices. We use the border substitution method combined with Koszul flattenings to prove the border rank lower bound of 2n^2-log(n)-1 for M_n.

Recommendations

• New lower bounds for the border rank of matrix multiplication
• A note on border rank
• New lower bounds for matrix multiplication and
• Equations for lower bounds on border rank
• The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)

Cited in

(19)

• Partial Degeneration of Tensors
• scientific article; zbMATH DE number 7689792 (Why is no real title available?)
• A note on border rank
• Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity
• The border support rank of two-by-two matrix multiplication is seven
• A note on VNP-completeness and border complexity
• On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
• The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
• Tensor surgery and tensor rank
• An introduction to the computational complexity of matrix multiplication
• A refined laser method and faster matrix multiplication
• The border rank of the multiplication of $2\times 2$ matrices is seven
• On the structure tensor of \(\mathfrak{sl}_n\)
• New lower bounds for the border rank of matrix multiplication
• Border rank is not multiplicative under the tensor product
• Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
• New lower bounds for the rank of matrix multiplication
• Towards a geometric approach to Strassen's asymptotic rank conjecture
• New lower bounds for matrix multiplication and

This page was built for publication: A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication

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