Volume 11 (2015)
Article 11 pp. 285-298
New Lower Bounds for the Border Rank of Matrix Multiplication
Received: October 1, 2013
Revised: December 12, 2014
Published: August 6, 2015
Revised: December 12, 2014
Published: August 6, 2015
Keywords: matrix multiplication complexity, border rank
Categories: complexity theory, matrix multiplication, lower bounds, rank, tensor rank, border rank, short
ACM Classification: F.2.1
AMS Classification: 68Q17, 68Q25, 15A99
Abstract: [Plain Text Version]
$
\newcommand\nnn{\mathbf{n}}
$
The border rank of the matrix multiplication operator for $\nnn\times \nnn$ matrices is a standard measure of its complexity. Using techniques from algebraic geometry and representation theory, we show the border rank is at least $2\nnn^2-\nnn$. Our bounds are better than the previous lower bound (due to Lickteig in 1985) of $3\nnn^2/2+ {\nnn}/{2}-1$ for all $\nnn\geq 3$. The bounds are obtained by finding new equations that bilinear maps of small border rank must satisfy, i.e., new equations for secant varieties of triple Segre products, that matrix multiplication fails to satisfy.
Licensed under a Creative Commons Attribution License (CC-BY)