A note on border rank

DOI10.1016/0020-0190(84)90023-1zbMath0539.68029OpenAlexW1997237738MaRDI QIDQ794161

Thomas Lickteig

Publication date: 1984

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(84)90023-1

zbMATH Keywords

tensor rankborder rankcomplexity of matrix multiplicationcomputational complexity of bilinear forms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

A lower bound for the border rank of a bilinear map ⋮ 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 ⋮ On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry ⋮ Geometry and the complexity of matrix multiplication ⋮ Tensor rank: matching polynomials and Schur rings ⋮ 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 ⋮ The border rank of the multiplication of $2\times 2$ matrices is seven ⋮ On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication ⋮ 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\) ⋮ Typical tensorial rank

Cites Work

• Unnamed Item
• Unnamed Item
• Rank and optimal computation of generic tensors
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Partial and Total Matrix Multiplication
• On the Asymptotic Complexity of Matrix Multiplication
• Further Pathologies in Algebraic Geometry