A $2{mathbf{n}}^2-{ ext{log}}_2({mathbf{n}})-1$ lower bound for the border rank of matrix multiplication Academic Article uri icon

abstract

  • © The Author(s) 2017. Let M(n) ϵ ℂn2 ⊗ℂn2⊗n2 denote the matrix multiplication tensor for n × n matrices. We use the border substitution method [2, 3, 6] combined with Koszul flattenings [8] to prove the border rank lower bound R(M(n,n,n)) ≥ 2n2 - ⌈log2(n)⌉-1.

author list (cited authors)

  • Landsberg, J. M., & Michałek, M.

citation count

  • 4

publication date

  • March 2017