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

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

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

(23)

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

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)