TY - GEN
T1 - Hypercontractivity, sum-of-squares proofs, and their applications
AU - Barak, Boaz
AU - Brandão, Fernando G.S.L.
AU - Harrow, Aram W.
AU - Kelner, Jonathan
AU - Steurer, David
AU - Zhou, Yuan
PY - 2012/6/26
Y1 - 2012/6/26
N2 - We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as ∥A∥ 2→q = max v≠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: 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(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) 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(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2→4 norm.
AB - We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as ∥A∥ 2→q = max v≠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: 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(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) 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(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2→4 norm.
KW - hypercontractive
KW - injective tensor norm
KW - semidefinite programming
KW - unique games conjecture
UR - http://www.scopus.com/inward/record.url?scp=84862597933&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862597933&partnerID=8YFLogxK
U2 - 10.1145/2213977.2214006
DO - 10.1145/2213977.2214006
M3 - Conference contribution
AN - SCOPUS:84862597933
SN - 9781450312455
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 307
EP - 326
BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12
Y2 - 19 May 2012 through 22 May 2012
ER -