A 2n(2) - log(2)(n)-1 Lower Bound for the Border Rank of Matrix Multiplication

Research output: Contribution to journalArticleScientificpeer-review

Researchers

  • Joseph M. Landsberg
  • Mateusz Michalek

Research units

  • Texas A&M Univ, Texas A&M University College Station, Texas A&M University System, Dept Math
  • Polish Acad Sci, Polish Academy of Sciences, Inst Phys

Abstract

Let M-<n > is an element of C-n2 circle times C-n2 circle times C-n2 denote the matrix multiplication tensor for n x 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,M-n,M-n >) >= 2n(2) - [log(2)(n)] - 1.

Details

Original languageEnglish
Pages (from-to)4722-4733
Number of pages12
JournalINTERNATIONAL MATHEMATICS RESEARCH NOTICES
Issue number15
Publication statusPublished - Aug 2018
MoE publication typeA1 Journal article-refereed

ID: 30273001