Asymptotic tensor rank of graph tensors: beyond matrix multiplication
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Asymptotic tensor rank of graph tensors : beyond matrix multiplication. / Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen.
I: Computational Complexity, Bind 28, Nr. 1, 2019, s. 57-111.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Asymptotic tensor rank of graph tensors
T2 - beyond matrix multiplication
AU - Christandl, Matthias
AU - Vrana, Péter
AU - Zuiddam, Jeroen
PY - 2019
Y1 - 2019
N2 - We present an upper bound on the exponent of the asymptotic behaviour of the tensor rank of a family of tensors defined by the complete graph on k vertices. For k≥ 4 , we show that the exponent per edge is at most 0.77, outperforming the best known upper bound on the exponent per edge for matrix multiplication (k = 3), which is approximately 0.79. We raise the question whether for some k the exponent per edge can be below 2/3, i.e. can outperform matrix multiplication even if the matrix multiplication exponent equals 2. In order to obtain our results, we generalize to higher-order tensors a result by Strassen on the asymptotic subrank of tight tensors and a result by Coppersmith and Winograd on the asymptotic rank of matrix multiplication. Our results have applications in entanglement theory and communication complexity.
AB - We present an upper bound on the exponent of the asymptotic behaviour of the tensor rank of a family of tensors defined by the complete graph on k vertices. For k≥ 4 , we show that the exponent per edge is at most 0.77, outperforming the best known upper bound on the exponent per edge for matrix multiplication (k = 3), which is approximately 0.79. We raise the question whether for some k the exponent per edge can be below 2/3, i.e. can outperform matrix multiplication even if the matrix multiplication exponent equals 2. In order to obtain our results, we generalize to higher-order tensors a result by Strassen on the asymptotic subrank of tight tensors and a result by Coppersmith and Winograd on the asymptotic rank of matrix multiplication. Our results have applications in entanglement theory and communication complexity.
KW - 05C99
KW - 05D40
KW - 15A69
KW - 68Q12
KW - 68Q17
KW - 81P45
KW - algebraic complexity
KW - Dicke tensors
KW - graph tensors
KW - matrix multiplication
KW - subrank
KW - tensor rank
UR - http://www.scopus.com/inward/record.url?scp=85063048708&partnerID=8YFLogxK
U2 - 10.1007/s00037-018-0172-8
DO - 10.1007/s00037-018-0172-8
M3 - Journal article
AN - SCOPUS:85063048708
VL - 28
SP - 57
EP - 111
JO - Computational Complexity
JF - Computational Complexity
SN - 1016-3328
IS - 1
ER -
ID: 222974519