Injective Tensor Norms: Hardness and Reductions

If a vector has one index and a matrix has two, then a tensor has k indices, where k could be 3 or more. In this talk, I’ll consider the injective tensor norm, which for k=1 is the length of a vector and for k=2 is the largest singular value of a matrix. Applications of calculating this norm include finding planted cliques, simulating quantum systems and finding the distortion of certain norm embeddings.

I’ll show that much of the difficulty of calculating the injective tensor norm is captured already when k=3, and I’ll prove a hardness result in this case, even for the task of finding a very crude approximation. Previous hardness results applied only to the case of 1/poly(dim) accuracy. These results are based on arXiv:1001.0017 (work with Ashley Montanaro), and use quantum techniques, although the presentation will not assume familiarity with anything quantum.

Time permitting, I’ll discuss a conjecture that would imply the existence of an algorithm whose complexity would match the above lower bound.