# Hypercontractivity, sum-of-squares proofs, and applications

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

*Invited to STOC 2012 special issue*

## abstract

We study the computational complexity of approximating the $2$-to-$q$ norm of linear operators (defined as $\|A\|_{2\to q} = \max_{v\neq 0}\|Av\|_q/\|v\|_2$) for $q > 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 $q \geq 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\to q$ norm. As a corollary, a good approximation to the $2\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(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 $2\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(\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 $\omega(1)$ rounds.We show reductions between computing the $2\to 4$ norm and computing the

*injective tensor norm*of a tensor, a problem with connections to quantum information theory. Three corollaries are:the $2\to 4$ norm is NP-hard to approximate to precision inverse-polynomial in the dimension,

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

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

## keywords

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