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
Keywords tensor rank, graph tensors, subrank, Dicke tensors, algebraic complexity, matrix multiplication
Persistent URL dx.doi.org/10.1007/s00037-018-0172-8
Journal Computational Complexity
Citation
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