Asymptotic tensor rank of graph tensors: beyond matrix multiplication

Matthias Christandl, Péter Vrana, Jeroen Zuiddam*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

11 Citations (Scopus)
176 Downloads (Pure)

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

Keywords

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

Cite this