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

Joseph M. Landsberg; Mateusz Michalek

doi:10.1093/imrn/rnx025

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

Joseph M. Landsberg^*
, Mateusz Michalek

^*Tämän työn vastaava kirjoittaja

Ei julkaistu Aalto-yliopiston affiliaatiolla

Texas A&M University, College Station
Polish Academy of Sciences

Tutkimustuotos: Lehtiartikkeli › Article › Scientific › vertaisarvioitu

17 Viittaukset (Web of Science)

Abstrakti

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.

Alkuperäiskieli	Englanti
Sivut	4722-4733
Sivumäärä	12
Julkaisu	International Mathematics Research Notices
Numero	15
DOI - pysyväislinkit	https://doi.org/10.1093/imrn/rnx025
Tila	Julkaistu - elok. 2018
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Rahoitus

This work was supported by National Science Foundation grant [DMS-1405348 to J.L.]; and Iuventus Plus grant [0301/IP3/2015/73 to M.M.] of the Polish Ministry of Science.

Pääsy asiakirjaan

10.1093/imrn/rnx025

Siteeraa tätä

@article{b6f2042831e14056882bd1c2f29844be,

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

abstract = "Let M- 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-) >= 2n(2) - [log(2)(n)] - 1.",

author = "Landsberg, \{Joseph M.\} and Mateusz Michalek",

year = "2018",

month = aug,

doi = "10.1093/imrn/rnx025",

language = "English",

pages = "4722--4733",

journal = "International Mathematics Research Notices",

issn = "1073-7928",

publisher = "Oxford University Press",

number = "15",

}

TY - JOUR

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

AU - Landsberg, Joseph M.

AU - Michalek, Mateusz

PY - 2018/8

Y1 - 2018/8

N2 - Let M- 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-) >= 2n(2) - [log(2)(n)] - 1.

AB - Let M- 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-) >= 2n(2) - [log(2)(n)] - 1.

U2 - 10.1093/imrn/rnx025

DO - 10.1093/imrn/rnx025

M3 - Article

SN - 1073-7928

SP - 4722

EP - 4733

JO - International Mathematics Research Notices

JF - International Mathematics Research Notices

IS - 15

ER -

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

Abstrakti

Rahoitus

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä