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.
| Original language | English |
|---|---|
| Journal | Computational Complexity |
| Volume | 28 |
| Issue number | 1 |
| Pages (from-to) | 57-111 |
| Number of pages | 55 |
| ISSN | 1016-3328 |
| DOIs | |
| Publication status | Published - 2019 |
Keywords
- 05C99
- 05D40
- 15A69
- 68Q12
- 68Q17
- 81P45
- algebraic complexity
- Dicke tensors
- graph tensors
- matrix multiplication
- subrank
- tensor rank