2019-03-11
Asymptotic tensor rank of graph tensors: Beyond matrix multiplication
Publication
Publication
Computational Complexity , Volume 28 - Issue 1 p. 57- 111
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.
| Additional Metadata | |
|---|---|
| , , , , , | |
| doi.org/10.1007/s00037-018-0172-8 | |
| Computational Complexity | |
| Position-Based Quantum Cryptography | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Christandl, M., Vrana, P., & Zuiddam, J. (2019). Asymptotic tensor rank of graph tensors: Beyond matrix multiplication. Computational Complexity, 28(1), 57–111. doi:10.1007/s00037-018-0172-8 |
|
