New lower bounds for the border rank of matrix multiplication

DOI10.4086/toc.2015.v011a011zbMath1336.68102arXiv1112.6007OpenAlexW2964226640MaRDI QIDQ2941634

Giorgio Ottaviani, Joseph M. Landsberg

Publication date: 21 August 2015

Published in: Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

border rankmatrix multiplication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Multilinear algebra, tensor calculus (15A69)

Related Items (35)

A note on VNP-completeness and border complexity ⋮ Local equations for equivariant evolutionary models ⋮ On Comon's and Strassen's conjectures ⋮ Skew Howe duality and random rectangular Young tableaux ⋮ Codimension one Fano distributions on Fano manifolds ⋮ Generalized varieties of sums of powers ⋮ 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\) ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry ⋮ Decomposition Algorithms for Tensors and Polynomials ⋮ On the structure tensor of \(\mathfrak{sl}_n\) ⋮ Tensor rank: matching polynomials and Schur rings ⋮ Effective identifiability criteria for tensors and polynomials ⋮ Tensor surgery and tensor rank ⋮ Concise tensors of minimal border rank ⋮ 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 ⋮ Tensor rank is not multiplicative under the tensor product ⋮ Plethysm and fast matrix multiplication ⋮ Unnamed Item ⋮ Hankel Tensor Decompositions and Ranks ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Algebraic boundaries among typical ranks for real binary forms of arbitrary degree ⋮ Equations for Lower Bounds on Border Rank ⋮ On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication ⋮ Flattenings and Koszul Young flattenings arising in complexity theory ⋮ Rank and border rank of Kronecker powers of tensors and Strassen's laser method ⋮ On secant dimensions and identifiability of flag varieties ⋮ Explicit tensors of border rank at least 2d−2 in K^d ⊗ K^d ⊗ K^d in arbitrary characteristic ⋮ Nontriviality of equations and explicit tensors in \(\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m\) of border rank at least \(2m - 2\) ⋮ Unnamed Item ⋮ 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

• The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
• Nontriviality of equations and explicit tensors in \(\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m\) of border rank at least \(2m - 2\)

This page was built for publication: New lower bounds for the border rank of matrix multiplication