PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1205.4484v3cs.CCcs.DSquant-ph

TL;DR

The paper studies the complexity of approximating hypercontractive 2→q norms and their links to Unique Games, Small-Set Expansion, sum-of-squares proofs, and tensor norms. It develops reductions and semidefinite-programming analyses to obtain hardness results, subexponential algorithms, and approximation guarantees. The results connect these norms to UGC-related complexity questions and quantum information problems.

  • Problem

    The paper asks how difficult it is to approximate 2→q norms and how this difficulty relates to Unique Games, Small-Set Expansion, and injective tensor norms.

  • Method

    The paper relates hypercontractive norms to graph expansion and injective tensor norms, and analyzes them using the Sum-of-Squares semidefinite-programming hierarchy.

  • Results

    The paper establishes hardness and subexponential approximation results for 2→q norms, constant-round SoS guarantees for key Unique Games instances, and reductions to injective tensor norms with quantum-information consequences.

  • Takeaways & Limitations

    Approximating the 2→4 norm provides evidence relevant to both the validity of UGC and the complexity of quantum separability-related tensor problems.

  • Takeaways & Limitations

    The SoS pseudo-expectation hierarchy converges to true expectations as the round count grows, but convergence is not guaranteed in finitely many steps.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies hypercontractive p→q norms for p<q, emphasizing their links to spikiness, coding geometry, and random-walk mixing. It addresses the comparatively limited understanding of their computational complexity.

  • For p<q, a large q-norm relative to the p-norm indicates that mass is concentrated on a small portion of entries.
  • Maximizing ∥f∥q/∥f∥2 over a subspace is equivalent to computing the 2→q norm of its projector.
  • The subspace maximization problem is a geometric analogue of finding the shortest word in a linear code.
  • For normalized graph adjacency or Markov operators, mixed-norm bounds are known as hypercontractive inequalities and can imply rapid random-walk mixing.
  • Compared with p≥q norms, much less is known about the computational complexity of p→q norms when p<q.

2 Our Results

The paper develops algorithms, hardness results, and reductions connecting 2→q norms to small-set expansion, semidefinite hierarchies, tensor norms, quantum information, and Unique Games. These connections yield both subexponential algorithms and strong conditional or unconditional barriers to approximation.

  • The work studies the computational complexity of approximating 2→4 and, more generally, 2→q norms while connecting them to UGC and quantum information theory.
  • Algorithms: For every 1<c<C, a poly(n) exp(n^(2/q))-time algorithm computes a (c,C)-approximation for operators with range R^n.
  • Algorithms: This yields a subexponential Small-Set Expansion algorithm matching the parameters of the prior ABS10 algorithm.
  • Tensor-SDP: Tensor-SDP provides constant-factor approximation on selected instances, including random operators when m≥Ω(n^2 log n), while the ratio is ω(1) when m=o(n^2).
  • Sum of Squares: The d-round SoS extension runs in n^O(d) time and, for d=O(log(n)/ε^2), gives an additive approximation bounded by ε∥A∥^2_{2→2}∥A∥^2_{2→∞}.
  • Small-set expansion: A regular graph is a small-set expander precisely in the paper’s sense when projection onto top eigenvectors has bounded 2→q norm, with explicit implications in both directions.
  • Tensor norms: The paper relates 2→4 norms to injective tensor norms, whose r=3 case is NP-hard and whose study is motivated by entanglement and many-body physics.
  • Hardness: Assuming ETH, approximating the 2→4 norm within exp(log^ε(m)) requires at least m^log^δ(m) time when 2ε+δ<1, even for projectors.

3 The SoS hierarchy

The Sum of Squares hierarchy relaxes polynomial optimization through pseudo-expectations that obey linearity, positivity, and normalization. Its bounded-degree certificates can be solved by semidefinite programming and certify key norm and Unique Games results.

  • Definition and intuition: The SoS hierarchy is an SDP relaxation for polynomial equations, optimizing a polynomial objective over level-r pseudo-expectation functionals.For r-round relaxations, constraints and pseudo-expectations are restricted to degree at most r.
  • Definition and intuition: Pseudo-expectations act like expectations of fictitious correlated random variables while retaining linearity and positivity for bounded-degree polynomials.They need not behave exactly like expectations of actual numerical variables, but genuine random-variable expectations satisfy the conditions at every level.
  • Certificates: SoS certificates prove upper bounds by deriving them from polynomial constraints using only linearity and positivity, without intermediate polynomials of degree larger than r.The relation P ⪯ Q ensures every feasible r-pseudo-expectation satisfies ˜P ≤ ˜Q.
  • Definition and intuition: A level-r pseudo-expectation functional is linear, normalized by ˜1 = 1, and nonnegative on squares of polynomials of degree at most r/2.These conditions define the core feasible region of the hierarchy.
  • Computational form: The r-round SoS relaxation can be solved in (mn · log(1/ε))^O(r) time, using a positive-semidefinite representation of the pseudo-expectation constraints.The functional can be represented by moments of monomials up to degree r, yielding an n^O(r)-scale formulation.

4 Overview of proofs

The paper’s proof overview combines a subexponential norm-approximation algorithm, SoS proof lifting, and reductions linking the 2→4 norm to graph expansion and tensor optimization.

  • Subexponential approximation: A subexponential algorithm restricts attention to low-dimensional subspaces, where the 2→q norm can be computed in exp(O(n^(2/q))) time.Large dimension forces a function with a large q-to-2 norm ratio, enabling dimension reduction before exhaustive optimization.
  • SoS proof lifting: SoS proofs lift one-dimensional sum-of-squares arguments into the relaxation domain to certify small objective values.The approach relies on nonnegativity of sums of squares and an SoS version of Cauchy–Schwarz.
  • Small-set expansion: For q=4, bounded projector 2→4 norm is equivalent to small-set expansion for graph top eigenspaces.The proof argues that a concentrated top-eigenspace function would spread large values from a small set to a much larger neighborhood, contradicting expansion.
  • Tensor and quantum connections: The 2→4 norm is connected to injective tensor optimization through linear-algebraic reductions and product-state optimization for a quantum measurement operator.The matrix A2,2 expresses the norm as a maximum over unit product states, while unrestricted optimization gives the operator norm.
  • Tensor and quantum connections: Further reductions relate Tensor-SDP to DPS, making the two relaxations essentially equivalent and allowing results from quantum information theory to transfer.The transfer includes approximation guarantees for 1-LOCC measurements under DPS.

5 The Tensor-SDP algorithm

Tensor-SDP is an SDP relaxation for optimizing the 2→4 norm and related degree-4 polynomials, with SoS extensions that certify bounds on selected instances.

  • Basic relaxation: Tensor-SDP replaces the 2→4 objective with a degree-4 polynomial optimization over fictitious random variables.Its basic version uses degree d=4 and extends naturally to optimizing arbitrary polynomials over the unit ball of L2(U).
  • Supported instances: Tensor-SDP performs well on random instances and on the projector to low-degree polynomials, where it yields a nontrivial approximation.The paper explicitly notes that its worst-case performance remains unknown.
  • SoS certification: A lifted hypercontractive inequality is proved by induction on the number of Boolean variables for low-degree Fourier polynomials.The induction decomposes f and g by the final variable and applies the hypothesis to four lower-degree terms.
  • SoS certification: The proof controls the cross terms using sum-of-squares nonnegativity before applying the induction hypothesis.Expanding 2(f0f1−g0g1)^2 bounds the mixed product terms by squared lower-degree expressions.

6 SoS succeeds on Unique Games integrality gaps

Eight rounds of the SoS hierarchy refute the canonical constant-alphabet Unique Games integrality-gap instances by lifting their soundness analyses. The proof combines invariance, hypercontractivity, influence decoding, and independent rounding in the lifted setting.

  • Theorem 6.1: 8 rounds of SoS output at most 1/100 on composed Unique Games instances whose best assignment satisfies at most an ε fraction of constraints.The result applies for sufficiently small ε and large k.
  • Lifting to SoS: The construction derives a level-4 fictitious random variable from a level-8 SoS solution and bounds its objective through low-degree Fourier structure.Influence decoding and simulated independent rounding address the weaker algebraic properties of fictitious random variables.
  • Proof strategy: The proof lifts prior soundness arguments into SoS, including invariance, influence decoding, hypercontractivity, and independent rounding.The lifted analysis is technically challenging because fictitious random variables do not obey all identities of ordinary variables.
  • Invariance principle: The SoS proof uses a fourth-moment invariance principle rather than the general smooth-functional version.It compares probability spaces agreeing on their first two moments, and fourth-moment invariance suffices for the applications.
  • Consequences: The same eight-round SoS approach yields relaxation values close to 1/k^Ω(ε) when log R ≫ (log k)^2/η for noisy-cube and short-code instances.The stated bound applies to both W and the short-code variant W′.

7 Hypercontractivity of random operators

This section analyzes Tensor-SDP for random linear operators, showing that its approximation ratio approaches 1 in a high-dimensional regime under distributional assumptions. The proof combines moment calculations, concentration inequalities, and the symmetry of semidefinite programming, while identifying the necessity of the PPT constraint.

  • The analysis assumes centered, suitably sub-gaussian entry distributions, including uniform random signs and standard Gaussian entries.The relevant ψ_p conditions and examples are introduced before the main theorem.
  • Tensor-SDP’s approximation ratio approaches 1 as m,n→∞ and n^2/m→0.The theorem holds with high probability for random matrices whose entries satisfy the stated distributional conditions.
  • The upper bound requires matrix concentration together with Tensor-SDP’s symmetry, rather than merely bounding an associated top eigenvalue.This is presented as a crucial distinction between the semidefinite-programming relaxation and a simpler eigenvalue calculation.
  • The lower bound uses fourth-moment expansions, sign-aligned vectors, and concentration to control ||A||_{2→4}.Dominant pairings reproduce the expansion of the relevant fourth-moment expression, while sign choices yield lower bounds under broad assumptions.
  • The denominator in the approximation bound cannot generally be improved, since a random sign matrix has 2→4 norm 1 when n=1.The discussion also compares this with a vector whose fourth-norm expression equals 1+2/n.
  • The PPT constraint is necessary for Tensor-SDP’s approximation to succeed, whereas eigenvalue bounds alone can be insufficient.The discussion interprets this separation in the language of quantum information and extends the point to higher hierarchy levels.

8 The 2-to-q norm and small-set expansion

The section characterizes small-set expansion through bounded 2→q norms of top-eigenspace projectors and reduces expansion testing to norm approximation.

  • Characterization: For even q≥4, a graph is a small-set expander exactly when the projector onto its top adjacency eigenvectors has bounded 2→q norm.The converse direction is identified as novel, while the forward direction was previously known.
  • Characterization: A norm bound implies small-set expansion, with ∥P⩾λ(G)∥2→q ≤ ε/δ^(q−2)/2q yielding ΦG(δ) ≥ 1−λ−ε².This is the section’s explicit norm-to-expansion implication.
  • Characterization: Conversely, ΦG(δ) > 1−c1λ^(2q)/(2−c2q) implies ∥P⩾λ(G)∥2→q ≤ 2.Thus sufficiently strong expansion certifies a bounded norm.
  • Algorithmic consequences: A good approximation to the 2→q norm yields an approximation of the small-set expansion parameter and would refute the Small-Set Expansion Hypothesis.The reduction uses the norm gap between Yes and No instances.
  • Proof strategy: The proof’s expansion-to-norm direction bounds high-value portions of an extremizing function using collision probabilities and iteratively constructed witness sets.Claim 8.3 produces a set T of size at least e|S| carrying squared mass at least β²/4.

9 Relating the 2-to-4 norm and the injective tensor norm

The section gives equivalent formulations of the 2→4 norm as injective tensor and convex optimization quantities, linking the problem to separable-state optimization in quantum information.

  • Equivalent formulations: The 2→4 norm is represented through injective tensor norms of 4-tensors and 3-tensors, as well as a linear maximization over a convex set.These formulations support both hardness and algorithmic applications.
  • Quantum connection: The quantum-information connection is methodological: separable-state arguments are imported to study a non-quantum 2→4 norm problem.No quantum algorithm is involved in these reductions.
  • Tensor norms: The injective tensor norm maximizes the absolute inner product with a product of L2-unit vectors.For symmetric tensors, the maximizing vectors can be taken equal.
  • Separable states: For an r-tensor, injective tensor norm computation is equivalent in difficulty to evaluating the support function of separable states on positive semidefinite arguments.The equivalence may require padding the tensor dimension to match the rank of the positive semidefinite matrix.
  • Sanity check: For r=2, the tensor formulation reduces to the familiar identity between the largest singular value squared and the largest eigenvalue of TT*.This illustrates the general tensor-to-separable-state correspondence in a matrix case.

9.2 Hardness of approximation for the 2-to-4 norm

The hardness section reduces separable-state gap problems and 3-SAT to distinguishing multiplicative gaps in the 2→4 norm, including for projectors.

  • 3-SAT hardness: The reduction transforms a 3-SAT instance into deciding whether ∥A∥2→4 is at least C or at most c, with polynomial dimension and inverse-polynomial multiplicative gap.The stated construction uses an m×m real matrix.
  • Core reduction: An efficiently constructible matrix A maps separable-state cases to 2→4 gaps: norm 1 in case Y versus (1−δ/2)^k in case N.The constructed matrix has size n^(4k)×n^(2k).
  • 3-SAT hardness: Known separable-state hardness supplies the starting promise: hSep(M)=1 versus hSep(M)≤1−1/n^c log(n), which transfers to the 2→4 norm.The reduction preserves efficient constructibility and produces a corresponding norm gap.
  • Gap amplification: Tensor powers amplify the separable-state separation to values 1 versus at most (3/4)^k.This amplification is applied across the relevant separable-state cut.
  • Projector hardness: The hardness extends essentially to projectors: a polynomial-time projector approximation would yield an approximation algorithm for general operators with bounded minimum singular value.The transfer uses Lemmas 9.7 and 9.8 before applying the hardness theorem.
  • Projector hardness: For any ℓ and ε>0, 3-SAT satisfiability reduces to distinguishing projector norms at most 3^(1/4)+ε from at least ℓ in dimension exp(√n polylog(n)).This gives the stated subexponential-time barrier for good approximation.

9.3 Algorithmic applications of equivalent formulations

The section develops Tensor-SDP and relates it to quantum separability relaxations, obtaining additive approximation guarantees while documenting hierarchy gaps and limitations.

  • Hierarchy equivalence: The PPT and extendability constraints translate optimal DPS solutions into valid Tensor-SDP pseudo-expectations.The construction uses symmetry, partial transpose, flattening, and polynomial coefficient maps.
  • Hierarchy equivalence: Level-r DPS relaxation on A2,2 is equivalent to Tensor-SDP(2r+2), connecting quantum separability relaxations with the Sum-of-Squares framework.The equivalence applies to the 2→4 norm formulation.
  • Approximation guarantees: Quantum separability analyses yield additive error ε using O(log(n)/ε²) Tensor-SDP rounds and runtime exp(O(log²(n)/ε²)).The same guarantee applies whether the implementation uses DPS or the SoS-based Tensor-SDP algorithm.
  • Gap instances: The r-extendable hierarchy cannot achieve a good multiplicative approximation for all M without r≥Ω(n).A constructed n²-dimensional instance exhibits the relevant gap.

10 Subexponential algorithm for the 2-to-q norm

The section gives an exp(n^(2/q))-time algorithm for constant-factor distinguishing approximation of the 2→q norm, and derives a subexponential algorithm for Small-Set Expansion. The approach searches for large-q-norm vectors in sufficiently large subspaces, with Sum-of-Squares available as an alternative to brute force.

  • Algorithm for the 2-to-q norm: exp(n^(2/q)) time yields a (c,C)-approximation for the 2→q norm of any operator with range in R^n.Here 1<c<C are arbitrary fixed constants, with an additional polynomial factor in n.
  • Algorithm for the 2-to-q norm: A subspace of sufficiently large dimension contains a readily findable vector whose q-norm is much larger than its 2-norm.Enumerating vectors in the subspace takes time exponential in its dimension.
  • Proof idea: The proof constructs coordinate-based vectors from an orthonormal basis and uses a single large coordinate to witness a large q-norm.The basis and coordinate calculations establish the existence of a vector with the required norm separation.
  • Algorithm for the 2-to-q norm: Brute-force enumeration distinguishes whether the operator’s 2→q norm is at most c or at least C after checking the image dimension and minimum singular value.If the minimum singular value exceeds c, the low-norm case is already excluded; otherwise the image dimension determines the remaining step.

Conclusions

The paper concludes by motivating further study of the complexity of approximating hypercontractive norms, especially the 2→4 norm and its relationship to Small-Set Expansion. It identifies multiple possible complexity-theoretic scenarios for these problems and their connection to the UGC.

  • Open questions: The 2→4 norm and its relation to Small-Set Expansion remain central questions for understanding the complexity of approximating hypercontractive norms.The paper specifically asks whether good 2→4-norm approximations can be obtained efficiently.
  • Open questions: The paper leaves open scenarios in which both problems are solvable in quasipolynomial time but not faster, with implications for the stated UGC.The supplied conclusion passage begins enumerating these scenarios but does not provide the full list.
  • Acknowledgments: The acknowledgments credit discussions, error correction, referee comments, and research support from multiple funding agencies.This contextual material does not state a scientific result.

A More facts about pseudo-expectation

This appendix records pseudo-expectation facts used in the paper, including order properties, degree reduction, and Cauchy–Schwarz and Hölder inequalities for fictitious random variables.

  • Order properties: P^2 ⪯ P holds exactly when 0 ⪯ P ⪯ 1, and every 0 ⪯ Q ⪯ P then satisfies Q^2 ⪯ Q.The proof uses positivity and the identity 1−P = P−P^2 +(1−P)^2.
  • Fictitious random variables: Applying degree-at-most-k polynomial transformations to a degree-d fictitious random variable produces a level-(d/k) fictitious random variable.This provides a way to reduce the available pseudo-expectation level under polynomial substitution.
  • Inequalities: The appendix establishes Cauchy–Schwarz and Hölder inequalities for fictitious random variables using pseudo-expectation identities and sum-of-squares inequalities.The supplied proof fragments show Cauchy–Schwarz leading to the stated Hölder corollary.
  • Proof techniques: The displayed proofs derive inequalities by expressing differences as square polynomials or applying Lemma A.4 repeatedly.These arguments preserve the relevant pseudo-expectation order relations.

B Norm bound implies small-set expansion

This section shows that bounding the 2→q norm of a graph’s top-eigenspace projector implies small-set expansion. The proof decomposes a set’s characteristic function into high- and low-eigenvalue components and bounds the relevant projection using norm duality.

  • Main implication: A bounded 2→q norm for the projector onto a graph’s top eigenspace yields a small-set expansion guarantee.The top eigenspace V⩾λ is spanned by eigenfunctions with eigenvalue at least λ.
  • Norm duality: Norm duality rewrites the 2→q norm as the dual q/(q−1)→2 norm of the transpose operator.For projection operators, the operator equals its transpose, simplifying the application to eigenspace projectors.
  • Proof decomposition: The characteristic function of a set is decomposed into its top-eigenspace projection and the component supported on eigenvalues below λ.The set measure then controls the norm of the projected component through the operator norm of the eigenspace.
  • Proof conclusion: Substituting the projection bound into the decomposition inequality gives the claimed expansion estimate.The final step is recorded as the conclusion of the lemma’s proof.

C Semidefinite Programming Hierarchies

This section compares different semidefinite programming hierarchies and discusses their properties.

  • The section compares different SDP hierarchies.
  • It discusses properties of the hierarchies under comparison.
  • The section frames the discussion around comparative analysis of SDP formulations.

C.1 Example of Max Cut

The section examines the SoS and Lasserre hierarchies through a Max Cut formulation. It defines both relaxations and describes constructions establishing their equivalence up to constant-factor differences in the number of levels.

  • Comparison of SoS and Lasserre: The SoS and Lasserre hierarchies are compared using Max Cut.The discussion uses a Lasserre formulation similar to one from prior work.
  • Comparison of SoS and Lasserre: The formulations are equivalent up to small constant factors in the number of hierarchy levels, with syntactic modifications extending the comparison to Unique Games.
  • Lasserre relaxation: The level-d Lasserre relaxation is formulated as a semidefinite program over vectors indexed by subsets of vertices.
  • Lasserre relaxation: The Lasserre constraints require inner products to agree whenever the corresponding symmetric differences of index sets agree.
  • SoS relaxation: The level-d SoS relaxation is formulated using a degree-d pseudo-expectation functional and a degree-d formal random variable.
  • From Lasserre to SoS: A Lasserre solution is converted to an SoS solution by multilinearizing polynomials, reducing squares x_i^2 to 1, and evaluating coefficients against vectors.The construction reduces polynomials modulo the ideal generated by x_i^2−1.
  • From SoS to Lasserre: An SoS solution is converted to a Lasserre solution through a positive-semidefinite moment matrix and vectors whose inner products depend only on parity of exponent sums.The construction uses the identity ˜(x^2P)=˜P for appropriately bounded-degree polynomials.
Loading 1205.4484v3…