Hypercontractivity, Sum-of-Squares Proofs, and their Applications

Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow +3

We study the computational complexity of approximating the 2->q norm of linear operators (defined as ||A||_{2->q} = sup_v ||Av||_q/||v||_2), as well as connections between this que…