A $2{\mathbf{n}}^2-{\text{log}}_2({\mathbf{n}})-1$ lower bound for the border rank of matrix multiplication

DOI10.1093/imrn/rnx025zbMath1431.15003arXiv1608.07486OpenAlexW2591902642MaRDI QIDQ4619419

Mateusz Michałek, Joseph M. Landsberg

Publication date: 6 February 2019

Published in: 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

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) Multilinear algebra, tensor calculus (15A69) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items (7)

A note on VNP-completeness and border complexity ⋮ An introduction to the computational complexity of matrix multiplication ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Partial Degeneration of Tensors ⋮ Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity ⋮ Unnamed Item ⋮ Towards a geometric approach to Strassen's asymptotic rank conjecture

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