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.

In: Computational Complexity, Vol. 28, No. 1, 2019, p. 57-111.

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

Harvard

Christandl, M, Vrana, P & Zuiddam, J 2019, 'Asymptotic tensor rank of graph tensors: beyond matrix multiplication', Computational Complexity, vol. 28, no. 1, pp. 57-111. https://doi.org/10.1007/s00037-018-0172-8

APA

Christandl, M., Vrana, P., & Zuiddam, J. (2019). Asymptotic tensor rank of graph tensors: beyond matrix multiplication. Computational Complexity, 28(1), 57-111. https://doi.org/10.1007/s00037-018-0172-8

Vancouver

Christandl M, Vrana P, Zuiddam J. Asymptotic tensor rank of graph tensors: beyond matrix multiplication. Computational Complexity. 2019;28(1):57-111. https://doi.org/10.1007/s00037-018-0172-8

Author

Christandl, Matthias ; Vrana, Péter ; Zuiddam, Jeroen. / Asymptotic tensor rank of graph tensors : beyond matrix multiplication. In: Computational Complexity. 2019 ; Vol. 28, No. 1. pp. 57-111.

Bibtex

@article{c8656270a0724edcbd44fee2264edc84,
title = "Asymptotic tensor rank of graph tensors: beyond matrix multiplication",
abstract = "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.",
keywords = "05C99, 05D40, 15A69, 68Q12, 68Q17, 81P45, algebraic complexity, Dicke tensors, graph tensors, matrix multiplication, subrank, tensor rank",
author = "Matthias Christandl and P{\'e}ter Vrana and Jeroen Zuiddam",
year = "2019",
doi = "10.1007/s00037-018-0172-8",
language = "English",
volume = "28",
pages = "57--111",
journal = "Computational Complexity",
issn = "1016-3328",
publisher = "Springer Basel AG",
number = "1",

}

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