Injective Tensor Norms: Hardness and Reductions


April 28, 2011


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.


Aram Harrow

Aram Harrow is a visiting Assistant Professor in the Department of Computer Science, University of Washington. In 2005, He received a PhD in Physics from MIT, and a Marie Curie international fellowship. Aram has held the post of lecturer at the University of Bristol (CS and Math Departments) since then.