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

^*Corresponding author for this work

Not published at Aalto University

Research output: Contribution to journal › Article › Scientific › peer-review

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.

Original language	English
Pages (from-to)	4722-4733
Number of pages	12
Journal	International Mathematics Research Notices
Issue number	15
DOIs	https://doi.org/10.1093/imrn/rnx025
Publication status	Published - Aug 2018
MoE publication type	A1 Journal article-refereed

Access to Document

10.1093/imrn/rnx025

Cite this

@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

Abstract

Access to Document

Fingerprint

Cite this