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

Boaz Barak, Fernando G.S.L. Brandão, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages307-326
Number of pages20
DOIs
StatePublished - Jun 26 2012
Externally publishedYes
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

Fingerprint

Information theory
Tensors
Polynomials
Eigenvalues and eigenfunctions
Computational complexity

Keywords

  • hypercontractive
  • injective tensor norm
  • semidefinite programming
  • unique games conjecture

ASJC Scopus subject areas

  • Software

Cite this

Barak, B., Brandão, F. G. S. L., Harrow, A. W., Kelner, J., Steurer, D., & Zhou, Y. (2012). Hypercontractivity, sum-of-squares proofs, and their applications. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 307-326). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214006

Hypercontractivity, sum-of-squares proofs, and their applications. / Barak, Boaz; Brandão, Fernando G.S.L.; Harrow, Aram W.; Kelner, Jonathan; Steurer, David; Zhou, Yuan.

STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. 2012. p. 307-326 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Barak, B, Brandão, FGSL, Harrow, AW, Kelner, J, Steurer, D & Zhou, Y 2012, Hypercontractivity, sum-of-squares proofs, and their applications. in STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 307-326, 44th Annual ACM Symposium on Theory of Computing, STOC '12, New York, NY, United States, 5/19/12. https://doi.org/10.1145/2213977.2214006
Barak B, Brandão FGSL, Harrow AW, Kelner J, Steurer D, Zhou Y. Hypercontractivity, sum-of-squares proofs, and their applications. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. 2012. p. 307-326. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214006
Barak, Boaz ; Brandão, Fernando G.S.L. ; Harrow, Aram W. ; Kelner, Jonathan ; Steurer, David ; Zhou, Yuan. / Hypercontractivity, sum-of-squares proofs, and their applications. STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. 2012. pp. 307-326 (Proceedings of the Annual ACM Symposium on Theory of Computing).
@inproceedings{b3905fc922164b5d8af8b5e976f0e0a9,
title = "Hypercontractivity, sum-of-squares proofs, and their applications",
abstract = "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.",
keywords = "hypercontractive, injective tensor norm, semidefinite programming, unique games conjecture",
author = "Boaz Barak and Brand{\~a}o, {Fernando G.S.L.} and Harrow, {Aram W.} and Jonathan Kelner and David Steurer and Yuan Zhou",
year = "2012",
month = "6",
day = "26",
doi = "10.1145/2213977.2214006",
language = "English (US)",
isbn = "9781450312455",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "307--326",
booktitle = "STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing",

}

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

ER -