Hypercontractivity, sum-of-squares proofs, and applications

with Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, Yuan Zhou. STOC 2012.

PDF

Invited to STOC 2012 special issue

abstract

We study the computational complexity of approximating the 22-to-qq norm of linear operators (defined as A2q=maxv0Avq/v2\|A\|_{2\to q} = \max_{v\neq 0}\|Av\|_q/\|v\|_2) for q>2q > 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:

  • For any constant even integer q4q \geq 4, a graph GG is a small-set expander if and only if the projector into the span of the top eigenvectors of GG's adjacency matrix has bounded 2q2\to q norm. As a corollary, a good approximation to the 2q2\to 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 computed in exp(n2/q)\exp(n^{2/q}) time, thus obtaining a different proof of the known subexponential algorithm for Small-Set Expansion.

  • Constant rounds of the Sum-of-Squares semidefinite programing hierarchy certify an upper bound on the 242\to 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(logO(1)n)\exp(\log^{O(1)} n) rounds (for the short code), as well as separates the Sum of Squares/Lasserre hierarchy from weaker hierarchies that were known to require ω(1)\omega(1) rounds.

  • We show reductions between computing the 242\to 4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are:

    1. the 242\to 4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension,

    2. the 242\to 4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(npolylog(n))\exp(\sqrt{n}\mathrm{poly}\log(n)), and

    3. known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 242\to 4 norm.

keywords

  • small-set expansion
  • sum-of-squares method
  • Unique Games Conjecture
  • quantum information
  • semidefinite programming
  • strong relaxations