Hypercontractivity, Sum-of-Squares Proofs, and their Applications

Abstract

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.

v1: 52 pages. v2: 53 pages, fixed small bugs in proofs of section 6 (on UG integrality gaps) and section 7 (on 2->4 norm of random matrices). Added comments about real-vs-complex random matrices and about the k-extendable vs k-extendable & PPT hierarchies. v3: fixed mistakes in random matrix section. The result now holds only for matrices with random entries instead of random columns

References in corpus (3)

• A complete family of separability criteria
• One-and-a-half quantum de Finetti theorems
• A quasipolynomial-time algorithm for the quantum separability problem

Cited by in corpus (27)

• The sum-of-squares hierarchy on the sphere, and applications in quantum information theory
• Convergence of SDP hierarchies for polynomial optimization on the hypersphere
• An improved semidefinite programming hierarchy for testing entanglement
• Semidefinite programming hierarchies for constrained bilinear optimization
• Limitations of semidefinite programs for separable states and entangled games
• Optimizing Mean Field Spin Glasses with External Field
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
• Tight Hardness of the Non-commutative Grothendieck Problem
• Estimating operator norms using covering nets
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Adversarially Robust Low Dimensional Representations
• Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique
• Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs
• Strongly Refuting Random CSPs Below the Spectral Threshold
• The Lasserre Hierarchy in Almost Diagonal Form
• An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers
• Inapproximability of Matrix $p\to q$ Norms
• Sum of squares bounds for the ordering principle
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
• A PTAS for ${\ell }_p$-Low Rank Approximation
• Strong Parallel Repetition for Unique Games on Small Set Expanders
• Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
• Finding Matrix Sequences with a High Asymptotic Growth Rate for Linear Constrained Switching Systems
• Optimal ${\ell }_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
• Conditional Linear Regression for Heterogeneous Covariances