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

DOI10.1093/IMRN/RNX025zbMATH Open1431.15003arXiv1608.07486OpenAlexW2591902642MaRDI QIDQ4619419FDOQ4619419

Authors: Mateusz Michalek, J. M. Landsberg 

Publication date: 6 February 2019

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

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.

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

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\)

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)

Cited In (19)

• Title not available (Why is that?)
• 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 border rank
• A note on VNP-completeness and border complexity
• On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
• A refined laser method and faster matrix multiplication
• Tensor surgery and tensor rank
• An introduction to the computational complexity of matrix multiplication
• The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
• 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
• Partial Degeneration of Tensors

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)