The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)

DOI10.1016/j.laa.2013.01.031zbMath1284.68301arXiv1211.6320OpenAlexW1737655677MaRDI QIDQ389730

Alex Massarenti, Emanuele Raviolo

Publication date: 21 January 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

complexity theorytensorsmatrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational aspects and applications of commutative rings (13P99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Related Items (15)

On the nuclear norm and the singular value decomposition of tensors ⋮ On Comon's and Strassen's conjectures ⋮ Codimension one Fano distributions on Fano manifolds ⋮ Generalized varieties of sums of powers ⋮ An introduction to the computational complexity of matrix multiplication ⋮ Decomposition Algorithms for Tensors and Polynomials ⋮ Effective identifiability criteria for tensors and polynomials ⋮ Corrigendum to ``The rank of \(n{\times}n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\) ⋮ Lower bound for ranks of invariant forms ⋮ On non-commutative rank and tensor rank ⋮ New lower bounds for the border rank of matrix multiplication ⋮ On secant dimensions and identifiability of flag varieties ⋮ On secant defectiveness and identifiability of Segre-Veronese varieties ⋮ Geometric complexity theory: an introduction for geometers ⋮ Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• Rank and optimal computation of generic tensors
• Gaussian elimination is not optimal
• New lower bounds for the border rank of matrix multiplication
• New Lower Bounds for the Rank of Matrix Multiplication

This page was built for publication: The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)