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

Understand

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 question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture (UGC).

• We show the following: 1.
• For any constant even integer q>=4, a graph $G$ is a "small-set expander" if and only if the projector into the span of the top eigenvectors of G's adjacency matrix has bounded 2->q norm.
• As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture--a close variant of the UGC.