## Asymptotic tensor rank of graph tensors: beyond matrix multiplication

Research output: Contribution to journal › Journal article › Research › peer-review

#### Standard

**Asymptotic tensor rank of graph tensors : beyond matrix multiplication.** / Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen.

Research output: Contribution to journal › Journal article › Research › peer-review

#### Harvard

*Computational Complexity*, vol. 28, no. 1, pp. 57-111. https://doi.org/10.1007/s00037-018-0172-8

#### APA

*Computational Complexity*,

*28*(1), 57-111. https://doi.org/10.1007/s00037-018-0172-8

#### 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