AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We prove upper bounds on the tensor rank of graph tensors. We present two methods. First, we introduce a surgery-like procedure to transform a good decomposition of a well-chosen tensor into a good decomposition of a tensor of interest. We illustrate the method with surgery on the cycle graph and obtain the first nontrivial rank results for large odd cycles and optimal asymptotic rank results for all cycles. Second, we generalize Strassen's laser method to higher-order tensors in order to show a nontrivial upper bound on the asymptotic rank for the complete graph. "Per edge" this improves on the best upper bound on the matrix multiplication exponent of Le Gall, for four or more vertices. In entanglement theory, our results amount to protocols for creating a network of entangled pairs from Greenberger-Horne-Zeilinger (GHZ) states by stochastic local operations and classical communication (SLOCC). In communication complexity theory, our results imply new bounds on the nondeterministic quantum communication complexity of equality games. Our work is inspired and tightly connected with the vast body of research on matrix multiplication.

This is joint work with Matthias Christandl (Copenhagen) and Péter Vrana (Budapest).

Christian Ikenmeyer

--email hidden

passcode not visible

logged in users only