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 finding an approximation with constant additive error. Previous hardness results applied only to the case of 1/poly(dim) accuracy. These results are based on joint work with Ashley Montanaro, and use quantum techniques, although the presentation will not assume familiarity with anything quantum.

I’ll conclude by discussing algorithms, and a conjecture that would imply the existence of an algorithm whose complexity would match the above lower bound.

发言人详细信息

Aram Harrow is a Research Assistant Professor in the CSE department of the University of Washington. He works on quantum algorithms, quantum information, and their connections to probability, convex geometry, complexity theory and other areas of math and computer science.

He graduated in 2005 from MIT with a PhD in physics, and then was a lecturer at the University of Bristol (in math and computer science) from 2005-2010 before moving to the University of Washington.

日期：
演讲者：
Aram Harrow
所属机构：
University of Washington