2016/09/30 by Matthias Christandl, Péter Vrana, Jeroen Zuiddam · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Complexity and Algorithms in Graphs #Exponent #Matrix (chemical analysis) #Matrix multiplication #Multiplication (music) #Quantum Computing Algorithms and Architecture #Rank (graph theory) #Strassen algorithm #Tensor (intrinsic definition) #Tensor decomposition and applications #Upper and lower bounds #cs.CC #math.CO #msc:05C65 #msc:15A69 #msc:68Q12 #msc:68Q17 #msc:81P45 #quant-ph
paper · pdf · doi:10.1007/s00037-018-0172-8
published as J. comput. complex. (2019) 28: 57
openalex created_date 2016/10/07 · openalex publication_date 2018/09/29 · arxiv created 2019/09/10 · arxiv updated 2019/09/11 · openalex updated_date 2026/08/05
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 generalise 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.