  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. We also show that such a good approximation can be obtained in
exp(n^(2/q)) time, thus obtaining a different proof of the known subexponential
algorithm for Small Set Expansion.
  2. Constant rounds of the "Sum of Squares" semidefinite programing hierarchy
certify an upper bound on the 2->4 norm of the projector to low-degree
polynomials over the Boolean cube, as well certify the unsatisfiability of the
"noisy cube" and "short code" based instances of Unique Games considered by
prior works. This improves on the previous upper bound of exp(poly log n)
rounds (for the "short code"), as well as separates the "Sum of
Squares"/"Lasserre" hierarchy from weaker hierarchies that were known to
require omega(1) rounds.
  3. We show reductions between computing the 2->4 norm and computing the
injective tensor norm of a tensor, a problem with connections to quantum
information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to
approximate to precision inverse-polynomial in the dimension, (ii) the 2->4
norm does not have a good approximation (in the sense above) unless 3-SAT can
be solved in time exp(sqrt(n) polylog(n)), and (iii) known algorithms for the
quantum separability problem imply a non-trivial additive approximation for the
2->4 norm.
