Asymptotic tensor rank of graph tensors: beyond matrix multiplication

Research output: Contribution to journalJournal articleResearchpeer-review


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 languageEnglish
JournalComputational Complexity
Issue number1
Pages (from-to)57-111
Number of pages55
Publication statusPublished - 2019

    Research areas

  • 05C99, 05D40, 15A69, 68Q12, 68Q17, 81P45, algebraic complexity, Dicke tensors, graph tensors, matrix multiplication, subrank, tensor rank

Number of downloads are based on statistics from Google Scholar and

No data available

ID: 222974519