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

Introduction

For a function $f\colon\Omega\to\varmathbb R$ on a (finite) probability space $\Omega$, the $p$-norm is defined as $\lVert f\rVert_{p}=(\operatorname*{\varmathbb{E}}_{\Omega}f^{p})^{1/p}$. We follow the convention to use expectation norms for functions (on probability spaces) and counting norms, denoted as ${\boldsymbol{\lVert}}v{\boldsymbol{\rVert}}_{p}=(\sum_{i=1}^{n}|v_{i}|^{p})^{1/p}$, for vectors $v\in\varmathbb R^{m}$. All normed spaces here will be finite dimensional. We distinguish between expectation and counting norms to avoid recurrent normalization factors. The $p\rightarrow q$ norm $\|A\|_{p\rightarrow q}$ of a linear operator $A$ between vector spaces of such functions is the smallest number $c\geqslant 0$ such that $\lVert Af\rVert_{q}\leqslant c\lVert f\rVert_{p}$ for all functions $f$ in the domain of $A$. We also define the $p\to q$ norm of a subspace $V$ to be the maximum of $\lVert f\rVert_{q}/\lVert f\rVert_{p}$ for $f\in V$; note that for $p=2$ this is the same as the norm of the projector operator into $V$.

In this work, we are interested in the case $p<q$ and we will call such $p\to q$ norms hypercontractive.We use this name because a bound of the form $\|A\|_{p\rightarrow q}\leqslant 1$ for $p<q$ is often called a hypercontractive inequality. Roughly speaking, for $p<q$, a function $f$ with large $\lVert f\rVert_{q}$ compared to $\lVert f\rVert_{p}$ can be thought of as “spiky” or somewhat sparse (i.e., much of the mass concentrated in small portion of the entries). Hence finding a function $f$ in a linear subspace $V$ maximizing $\lVert f\rVert_{q}/\lVert f\rVert_{2}$ for some $q>2$ can be thought of as a geometric analogue of the problem finding the shortest word in a linear code. This problem is equivalent to computing the $2\to q$ norm of the projector $P$ into $V$ (since $\lVert Pf\rVert_{2}\leqslant\lVert f\rVert_{2}$). Also when $A$ is a normalized adjacency matrix of a graph (or more generally a Markov operator), upper bounds on the $p\to q$ norm are known as mixed-norm, Nash or hypercontractive inequalities and can be used to show rapid mixing of the corresponding random walk (e.g., see the surveys [Gro75, SC97]). Such bounds also have many applications to theoretical computer science, which are described in the survey [Bis11].

However, very little is known about the complexity of computing these norms. This is in contrast to the case of $p\to q$ norms for $p\geqslant q$, where much more is known both in terms of algorithms and lower bounds, see [Ste05, KNS08, BV11].

Our Results

We initiate a study of the computational complexity of approximating the $2\to 4$ (and more generally $2\to q$ for $q>2$) norm. While there are still many more questions than answers on this topic, we are able to show some new algorithmic and hardness results, as well as connections to both Khot’s unique games conjecture [Kho02] (UGC) and questions from quantum information theory. In particular our paper gives some conflicting evidence regarding the validity of the UGC and its close variant— the small set expansion hypothesis (SSEH) of [RS10]. (See also our conclusions section.)

First, we show in Theorem 2.5 that approximating the $2\to 4$ problem to within any constant factor cannot be done in polynomial time (unless SAT can be solved in $\exp(o(n))$ time) but yet this problem is seemingly related to the Unique Games and Small-Set Expansion problems. In particular, we show that approximating the $2\to 4$ norm is Small-Set Expansion- hard but yet has a subexponential algorithm closely related to the [ABS10] algorithm for Unique Games and Small-Set Expansion. Thus the computational difficulty of this problem can be considered as some indirect evidence supporting the validity of the UGC (or perhaps some weaker variants of it). To our knowledge, this is the first evidence of this kind for the UGC.

On the other hand, we show that a natural polynomial-time algorithm (based on an SDP hierarchy) that solves the previously proposed hard instances for Unique Games. The previous best algorithms for some of these instances took almost exponential ( $\exp(\exp(\log^{\Omega(1)}n))$ ) time, and in fact they were shown to require super-polynomial time for some hierarchies. Thus this result suggests that this algorithm could potentially refute the UGC, and hence can be construed as evidence opposing the UGC’s validity.

We show several algorithmic results for the $2\to 4$ (and more generally $2\to q$) norm.

For $q\geqslant 2$, we say that an algorithm provides a $(c,C)$-approximation for the $2\to q$ norm if on input an operator $A$, the algorithm can distinguish between the case that $\lVert A\rVert_{2\to q}\leqslant c\sigma$ and the case that $\lVert A\rVert_{2\to q}\geqslant C\sigma$, where $\sigma=\sigma_{\min}(A)$ is the minimum nonzero singular value of $A$. (Note that since we use the expectation norm, $\lVert Af\rVert_{q}\geqslant\lVert Af\rVert_{2}\geqslant\sigma\lVert f\rVert_{2}$ for every function $f$ orthogonal to the Kernel of $A$.) We say that an algorithm provides a good approximation for the $2\to q$ norm if it provides a $(c,C)$-approximation for some (dimension independent) constants $c<C$. The motivation behind this definition is to capture the notion of a dimension independent approximation factor, and is also motivated by Theorem 2.4 below, that relates a good approximation for the $2\to q$ norm to solving the Small-Set Expansion problem.

For every $1<c<C$, there is a $\operatorname{poly}(n)\exp(n^{2/q})$-time algorithm that computes a $(c,C)$-approximation for the $2\to q$ norm of any linear operator whose range is $\varmathbb R^{n}$.

Combining this with our results below, we get as a corollary a subexponential algorithm for the Small-Set Expansion problem matching the parameters of [ABS10]’s algorithm. We note that this algorithm can be achieved by the “Sum of Squares” SDP hierarchy described below (and probably weaker hierarchies as well, although we did not verify this).

1.2 Polynomial algorithm for specific instances

We study a natural semidefinite programming (SDP) relaxation for computing the $2\to 4$ norm of a given linear operator which we call Tensor-SDP.We use the name Tensor-SDP for this program since it will be a canonical relaxation of the polynomial program $\max_{\lVert x\rVert_{2}=1}{\langle T,x^{\otimes 4}\rangle}$ where $T$ is the $4$-tensor such that $\langle T,x^{\otimes 4}\rangle=\lVert Ax\rVert_{4}^{4}$. See Section 4.5 for more details. While Tensor-SDP is very unlikely to provide a poly-time constant-factor approximation for the $2\to 4$ norm in general (see Theorem 2.5 below), we do show that it provides such approximation on two very different types of instances:

We show that Tensor-SDP certifies a constant upper bound on the ratio $\|A\|_{2\rightarrow 4}/\lVert A\rVert_{2\to 2}$ where $A:\varmathbb R^{n}\to\varmathbb R^{m}$ is a random linear operator (e.g., obtained by a matrix with entries chosen as i.i.d Bernoulli variables) and $m\geqslant\Omega(n^{2}\log n)$. In contrast, if $m=o(n^{2})$ then this ratio is $\omega(1)$, and hence this result is almost tight in the sense of obtaining “good approximation” in the sense mentioned above. We find this interesting, since random matrices seem like natural instances; indeed for superficially similar problems such shortest codeword, shortest lattice vector (or even the $1\to 2$ norm), it seems hard to efficiently certify bounds on random operators.

We show that Tensor-SDP gives a good approximation of the $2\to 4$ norm of the operator projecting a function $f:\{\pm 1\}^{n}\to\varmathbb R$ into its low-degree component:

Let $\mathcal{P}_{d}$ be the linear operator that maps a function $f:\{\pm 1\}^{n}\to\varmathbb R$ of the form $f=\sum_{\alpha\subseteq[n]}\hat{f}_{\alpha}\chi_{\alpha}$ to its low-degree part $f^{\prime}=\sum_{|\alpha|\leqslant d}\hat{f}_{\alpha}\chi_{\alpha}$ (where $\chi_{\alpha}(x)=\prod_{i\in\alpha}x_{i}$). Then $\textup{{Tensor-SDP}}(\mathcal{P}_{d})\leqslant 9^{d}$.

The fact that $\mathcal{P}_{d}$ has bounded $2\to 4$ norm is widely used in the literature relating to the UGC. Previously, no general-purpose algorithm was known to efficiently certify this fact.

1.3 Quasipolynomial algorithm for additive approximation

We also consider the generalization of Tensor-SDP to a natural SDP hierarchy. This is a convex relaxation that starts from an initial SDP and tightens it by adding additional constraints. Such hierarchies are generally paramaterized by a number $r$ (often called the number of rounds), where the $1^{\text{st}}$ round corresponds to the initial SDP, and the $n^{\text{th}}$ round (for discrete problems where $n$ is the instance size) corresponds to the exponential brute force algorithm that outputs an optimal answer. Generally, the $r^{\text{th}}$-round of each such hierarchy can be evaluated in $n^{O(r)}$ time (though in some cases $n^{O(1)}2^{O(r)}$ time suffices [BRS11]). See Section 3, as well as the surveys [CT10, Lau03] and the papers [SA90, LS91, RS09, KPS10] for more information about these hierarchies.

We call the hierarchy we consider here the Sum of Squares (SoS) hierarchy. It is not novel but rather a variant of the hierarchies studied by several authors including Shor [Sho87], Parrilo [Par00, Par03], Nesterov [Nes00] and Lasserre [Las01]. (Generally in our context these hierarchies can be made equivalent in power, though there are some subtleties involved; see [Lau09] and Appendix C for more details.) We describe the SoS hierarchy formally in Section 3. We show that Tensor-SDP’s extension to several rounds of the SoS hierarchy gives a non-trivial additive approximation:

Let $\textup{{Tensor-SDP}}^{(d)}$ denote the $n^{O(d)}$-time algorithm by extending Tensor-SDP to $d$ rounds of the Sum-of-Squares hierarchy. Then for all $\varepsilon$, there is $d=O(\log(n)/\varepsilon^{2})$ such that

The term $\|A\|_{2\rightarrow 2}^{2}\|A\|_{2\rightarrow\infty}^{2}$ is a natural upper bound on $\|A\|_{2\rightarrow 4}^{4}$ obtained using Hölder’s inequality. Since $\|A\|_{2\rightarrow 2}$ is the largest singular value of $A$, and $\|A\|_{2\rightarrow\infty}$ is the largest 2-norm of any row of $A$, they can be computed quickly. Theorem 2.3 shows that one can improve this upper bound by a factor of $\varepsilon$ using run time $\exp(\log^{2}(n)/\varepsilon^{2})$). Note however that in the special case (relevant to the UGC) that $A$ is a projector to a subspace $V$, $\lVert A\rVert_{2\to 2}=1$ and $\lVert A\rVert_{2\to\infty}\geqslant\sqrt{\dim(V)}$ (see Lemma 10.1), which unfortunately means that Theorem 2.3 does not give any new algorithms in that setting.

Despite Theorem 2.3 being a non-quantum algorithm for for an ostensibly non-quantum problem, we actually achieve it using the results of Brandão, Christandl and Yard [BaCY11] about the quantum separability problem. In fact, it turns out that the SoS hierarchy extension of Tensor-SDP is equivalent to techniques that have been used to approximate separable states [DPS04]. We find this interesting both because there are few positive general results about the convergence rate of SDP hierarchies, and because the techniques of [BaCY11], based on entanglement measures of quantum states, are different from typical ways of proving correctness of semidefinite programs, and in particular different techniques from the ones we use to analyze Tensor-SDP in other settings. This connection also means that integrality gaps for Tensor-SDP would imply new types of entangled states that pass most of the known tests for separability.

2 Reductions

We relate the question of computing the hypercontractive norm with two other problems considered in the literature: the small set expansion problem [RS10, RST10], and the injective tensor norm question studied in the context of quantum information theory [HM10, BaCY11].

Khot’s Unique Games Conjecture [Kho02] (UGC) has been the focus of intense research effort in the last few years. The conjecture posits the hardness of approximation for a certain constraint-satisfaction problem, and shows promise to settle many open questions in the theory of approximation algorithms. Many works have been devoted to studying the plausibility of the UGC, as well as exploring its implications and obtaining unconditional results inspired or motivated by this effort. Tantalizingly, at the moment we have very little insight on whether this conjecture is actually true, and thus producing evidence on the UGC’s truth or falsity is a central effort in computational complexity. Raghavendra and Steurer [RS10] proposed a hypothesis closely related to the UGC called the Small-Set Expansion hypothesis (SSEH). Loosely speaking, the SSEH states that it is NP-hard to certify that a given graph $G=(V,E)$ is a small-set expander in the sense that subsets with size $o(|V|)$ vertices have almost all their neighbors outside the set. [RS10] showed that SSEH implies UGC. While a reduction in the other direction is not known, all currently known algorithmic and integrality gap results apply to both problems equally well (e.g., [ABS10, RST12]), and thus the two conjectures are likely to be equivalent.

We show, loosely speaking, that a graph is a small-set expander if and only if the projection operator to the span of its top eigenvectors has bounded $2\to 4$ norm. To make this precise, if $G=(V,E)$ is a regular graph, then let $P_{\geqslant\lambda}(G)$ be the projection operator into the span of the eigenvectors of $G$’s normalized adjacency matrix with eigenvalue at least $\lambda$, and $\Phi_{G}(\delta)$ be $\min_{S\subseteq V,|S|\leqslant\delta|V|}\operatorname*{\varmathbb{P}}_{(u,v)\in E}[v\not\in S|u\in S]$.

Then we relate small-set expansion to the $2\rightarrow 4$ norm (indeed the $2\rightarrow q$ norm for even $q\geqslant 4$) as follows:

For every regular graph $G$, $\lambda>0$ and even $q$,

(Norm bound implies expansion) For all $\delta>0,\varepsilon>0$, $\|P_{\geqslant\lambda}(G)\|_{2\to q}\leqslant\varepsilon/\delta^{(q-2)/2q}$ implies that $\Phi_{G}(\delta)\geqslant 1-\lambda-\varepsilon^{2}$.

(Expansion implies norm bound) There are constants $c_{1},c_{2}>0$ such that for all $\delta>0$, $\Phi_{G}(\delta)>1-c_{1}\lambda^{2q}2^{-c_{2}q}$ implies $\|P_{\geqslant\lambda}(G)\|_{2\rightarrow q}\leqslant 2/\sqrt{\delta}$.

While one direction (bounded hypercontractive norm implies small-set expansion) was already known,While we do not know who was the first to point out this fact explicitly, within theoretical CS it was implicitly used in several results relating the Bonami-Beckner-Gross hypercontractivity of the Boolean noise operator to isoperimetric properties, with one example being O’Donnell’s proof of the soundness of [KV05]’s integrality gap (see [KV05, Sec 9.1]). to our knowledge the other direction is novel. As a corollary we show that the SSEH implies that there is no good approximation for the $2\to 4$ norm.

2.2 Hypercontractivity and the injective tensor norm

We are able to make progress in understanding both the complexity of the $2\rightarrow 4$ norm and the quality of our SDP relaxation by relating the $2\rightarrow 4$ norm to several natural questions about tensors. An $r$-tensor can be thought of as an $r$-linear form on $\varmathbb R^{n}$, and the injective tensor norm $\|\cdot\|_{\operatorname{inj}}$ of a tensor is given by maximizing this form over all unit vector inputs. See Section 9 for a precise definition. When $r=1$, this norm is the 2-norm of a vector and when $r=2$, it is the operator norm (or $2\!\rightarrow\!2$-norm) of a matrix, but for $r=3$ it becomes NP-hard to calculate. One motivation to study this norm comes from quantum mechanics, where computing it is equivalent to a number of long-studied problems concerning entanglement and many-body physics [HM10]. More generally, tensors arise in a vast range of practical problems involving multidimensional data [vL09] for which the injective tensor norm is both of direct interest and can be used as a subroutine for other tasks, such as tensor decomposition [dlVKKV05].

It is not hard to show that $\|A\|_{2\rightarrow 4}^{4}$ is actually equal to $\lVert T\rVert_{{\rm inj}}$ for some $4$-tensor $T=T_{A}$. Not all $4$-tensors can arise this way, but we show that the injective tensor norm problem for general tensors can be reduced to those of the form $T_{A}$. Combined with known results about the hardness of tensor computations, this reduction implies the following hardness result. To formulate the theorem, recall that the Exponential Time Hypothesis (ETH) [IPZ98] states that 3-SAT instances of length $n$ require time $\exp(\Omega(n))$ to solve.

Assuming ETH, then for any $\varepsilon,\delta$ satisfying $2\varepsilon+\delta<1$, the $2\rightarrow 4$ norm of an $m\times m$ matrix $A$ cannot be approximated to within a $\exp(\log^{\varepsilon}(m))$ multiplicative factor in time less than $m^{\log^{\delta}(m)}$ time. This hardness result holds even with $A$ is a projector.

While we are primarily concerned with the case of $\Omega(1)$ approximation factor, we note that poly-time approximations to within multiplicative factor $1+1/n^{1.01}$ are not possible unless $\textbf{P}=\textbf{NP}$. This, along with Theorem 2.5, is restated more formally as Theorem 9.4 in Section 9.2. Theorem 2.5 yields as a corollary that, assuming ETH, there is no polynomial-time algorithm obtaining a good approximation for the $2\rightarrow 4$ norm. We note that these results hold under weaker assumptions than the ETH; see Section 9.2 as well.

Previously no hardness results were known for the $2\rightarrow 4$ norm, or any $p\rightarrow q$ norm with $p<q$, even for calculating the norms exactly. However, hardness of approximation results for $1+1/\operatorname{poly}(n)$ multiplicative error have been proved for other polynomial optimization problems [BTN98].

3 Relation to the Unique Games Conjecture

Our results and techniques have some relevance to the unique games conjecture. Theorem 2.4 shows that obtaining a good approximation for the $2\to q$ norm is Small-Set Expansion hard, but Theorem 2.1 shows that this problem is not “that much harder” than Unique Games and Small-Set Expansion since it too has a subexponential algorithm. Thus, the $2\to q$ problem is in some informal sense “of similar flavor” to the Unique Games/ Small-Set Expansion. On the other hand, we actually are able to show in Theorem 2.5 hardness (even if only quasipolynomial) of this problem, whereas a similar result for Unique Games or Small-Set Expansion would be a major breakthrough. So there is a sense in which these results can be thought of as some “positive evidence” in favor of at least weak variants of the UGC. (We emphasize however that there are inherent difficulties in extending these results for Unique Games, and it may very well be that obtaining a multiplicative approximation to the $2\to 4$ of an operator is significantly harder problem than Unique Games or Small-Set Expansion.) In contrast, our positive algorithmic results show that perhaps the $2\to q$ norm can be thought of as a path to refuting the UGC. In particular we are able to extend our techniques to show a polynomial time algorithm can approximate the canonical hard instances for Unique Games considered in prior works.

(Informal) Eight rounds of the SoS relaxation certifies that it is possible to satisfy at most $1/100$ fraction of the constraints of Unique Games instances of the “quotient noisy cube” and “short code” types considered in [RS09, KS09, KPS10, BGH+11]

These instances are the same ones for which previous works showed that weaker hierarchies such as “SDP+Sherali Adams” and “Approximate Lasserre” require $\omega(1)$ rounds to certify that one cannot satisfy almost all the constraints [KV05, RS10, KS09, BGH+11]. In fact, for the “short code” based instances of [BGH+11] there was no upper bound known better than $\exp(\log^{\Omega(1)}n)$ on the number of rounds required to certify that they are not almost satisfiable, regardless of the power of the hierarchy used.

This is significant since the current best known algorithms for Unique Games utilize SDP hierarchies [BRS11, GS11],Both these works showed SDP-hierarchy-based algorithms matching the performance of the subexponential algorithm of [ABS10]. [GS11] used the Lasserre hierarchy, while [BRS11] used the weaker “SDP+Sherali-Adams” hierarchy. and the instances above were the only known evidence that polynomial time versions of these algorithms do not refute the unique games conjecture. Our work also show that strong “basis independent” hierarchies such as Sum of Squares [Par00, Par03] and Lasserre [Las01] can in fact do better than the seemingly only slightly weaker variants.The only other result of this kind we are aware of is [KMN11], that show that Lasserre gives a better approximation ratio than the linear programming Sherali-Adams hierarchy for the knapsack problem. We do not know if weaker semidefinite hierarchies match this ratio, although knapsack of course has a simple dynamic programming based PTAS.

The SoS hierarchy

For our algorithmic results in this paper we consider a semidefinite programming (SDP) hierarchy that we call the Sum of Squares (SoS) hierarchy. This is not a novel algorithm and essentially the same hierarchies were considered by many other researchers (see the survey [Lau09]). Because different works sometimes used slightly different definitions, in this section we formally define the hierarchy we use as well as explain the intuition behind it. While there are some subtleties involved, one can think of this hierarchy as equivalent in power to the programs considered by Parrilo, Lasserre and others, while stronger than hierarchies such “SDP+Sherali-Adams” and “Approximate Lasserre” considered in [RS09, KPS10, BRS11].

The SoS SDP is a relaxation for polynomial equations. That is, we consider a system of the following form: maximize $P_{0}(x)$ over $x\in\varmathbb R^{n}$ subject to $P_{i}^{2}(x)=0$ for $i=1\ldots m$ and $P_{0},\ldots,P_{m}$ polynomials of degree at most $d$.This form is without loss of generality, as one can translate an inequality constraint of the form $P_{i}(x)\geqslant 0$ into the equality constraint $(P_{i}(x)-y^{2})^{2}=0$ where $y$ is some new auxiliary variable. It is useful to show equivalences between various hierarchy formulations; see also Appendix C. For $r\geqslant 2d$, the $r$-round SoS SDP optimizes over $x_{1},\ldots,x_{n}$ that can be thought of as formal variables rather than actual numbers. For these formal variables, expressions of the form $P(x)$ are well defined and correspond to a real number (which can be computed from the SDP solution) as long as $P$ is a polynomial of degree at most $r$. These numbers obey the linearity property which is that $(P+Q)(x)=P(x)+Q(x)$, and, most importantly, the positivity property that $P^{2}(x)\geqslant 0$ for every polynomial $P$ of degree at most $r/2$. These expressions satisfy all initial constraints (i.e., $P_{i}^{2}(x)=0$ for $i=1\ldots m$) and the value of the SDP is set to be the expression $P_{0}(x)$. The above means that to show that the SoS relaxation has value at most $v$ it is sufficient to give any proof that derives from the constraints $\{P_{i}^{2}(x)=0\}_{i=1..m}$ the conclusion that $P_{0}(x)\leqslant v$ using only the linearity and positivity properties, without using any polynomials of degree larger than $r$ in the intermediate steps. In fact, such a proof always has the form

where $R_{1},\ldots,R_{k},Q_{1},\ldots,Q_{m}$ are arbitrary polynomials satisfying $\deg R_{i}\leqslant r/2,\deg P_{i}Q_{i}\leqslant r$. The polynomial $\sum_{i}R_{i}(x)^{2}$ is a SoS (sum of squares) and optimizing over such polynomials (along with the $Q_{1},\ldots,Q_{m}$) can be achieved with a semi-definite program.

We can now present our formal definition of pseudo-expectation and the SoS hierarchy:We use the name “Sum of Squares” since the positivity condition below is the most important constraint of this program. However, some prior works used this name for the dual of the program we define here. As we show in Appendix C, in many cases of interest to us there is no duality gap.

The main difference between the SoS hierarchy and weaker SDP hierarchies considered in the literature such as SDP+Sherali Adams and the Approximate Lasserre hierarchies [RS09, KPS10] is that the SoS hierarchy treats all polynomials equally and hence is agnostic to the choice of basis. For example, the approximate Lasserre hierarchy can also be described in terms of pseudo-expectations, but these pseudo-expectations are only defined for monomials, and are allowed some small error. While they can be extended linearly to other polynomials, for non-sparse polynomials that error can greatly accumulate.

1 Basic properties of pseudo-expectation

For two polynomials $P$ and $Q$, we write $P\preceq Q$ if $Q=P+\sum_{i=1}^{m}R_{i}^{2}$ for some polynomials $R_{1},\ldots,R_{m}$.

We would like to understand how polynomials behave on linear subspaces of $\varmathbb R^{n}$. A map $P\colon\varmathbb R^{n}\to\varmathbb R$ is polynomial over a linear subspace $V\subseteq\varmathbb R^{n}$ if $P$ restricted to $V$ agrees with a polynomial in the coefficients for some basis of $V$. Concretely, if $g_{1},\ldots,g_{m}$ is an (orthonormal) basis of $V$, then $P$ is polynomial over $V$ if $P(f)$ agrees with a polynomial in $\langle f,g_{1}\rangle,\ldots,\langle f,g_{m}\rangle$. We say that $P\preceq Q$ holds over a subspace $V$ if $P-Q$, as a polynomial over $V$, is a sum of squares.

2 Why is this SoS hierarchy useful?

While the proof of (3.3) is fairly simple, we find the result— that hypercontractivity of polynomials is efficiently certifiable—somewhat surprising. The reason is that hypercontractivity serves as the basis of the integrality gaps results which are exactly instances of maximization problems where the objective value is low but this is supposedly hard to certify. In particular, we consider integrality gaps for Unique Games considered before in the literature. All of these instances follow the framework initiated by Khot and Vishnoi [KV05]. Their idea was inspired by Unique Games hardness proofs, with the integrality gap obtained by composing an initial instance with a gadget. The proof that these instances have “cheating” SDP solutions is obtained by “lifting” the completeness proof of the gadget. On the other hand, the soundness property of the gadget, combined with some isoperimetric results, showed that the instances do not have real solutions. This approach of lifting completeness proofs of reductions was used to get other integrality gap results as well [Tul09]. We show that the SoS hierarchy allows us to lift a certain soundness proof for these instances, which includes a (variant of) the invariance principle of [MOO05], influence-decoding a la [KKMO04], and hypercontractivity of low-degree polynomials. It turns out all these results can be proven via sum-of-squares type arguments and hence lifted to the SoS hierarchy.

Overview of proofs

We now give a very high level overview of the tools we use to obtain our results, leaving details to the later sections and appendices.

Our subexponential algorithm for obtaining a good approximation for the $2\to q$ norm is extremely simple. It is based on the observation that a subspace $V\subseteq\varmathbb R^{n}$ of too large a dimension must contain a function $f$ such that $\lVert f\rVert_{q}\gg\lVert f\rVert_{2}$. For example, if $\dim(V)\gg\sqrt{n}$, then there must be $f$ such that $\lVert f\rVert_{4}\gg\lVert f\rVert_{2}$. This means that if we want to distinguish between, say, the case that $\|V\|_{2\rightarrow 4}\leqslant 2$ and $\|V\|_{2\rightarrow 4}\geqslant 3$, then we can assume without loss of generality that $\dim(V)=O(\sqrt{n})$ in which case we can solve the problem in $\exp(O(\sqrt{n}))$ time. To get intuition, consider the case that $V$ is spanned by an orthonormal basis $f^{1},\ldots,f^{d}$ of functions whose entries are all in $\pm 1$. Then clearly we can find coefficients $a_{1},\ldots,a_{d}\in\{\pm 1\}$ such that the first coordinate of $g=\sum a_{j}f^{j}$ is equal to $d$, which means that its $4$-norm is at least $(d^{4}/n)^{1/4}=d/n^{1/4}$. On the other hand, since the basis is orthonormal, the $2$-norm of $g$ equals $\sqrt{d}$ which is $\ll d/n^{1/4}$ for $d\gg\sqrt{n}$.

Note the similarity between this algorithm and [ABS10]’s algorithm for Small-Set Expansion, that also worked by showing that if the dimension of the top eigenspace of a graph is too large then it cannot be a small-set expander. Indeed, using our reduction of Small-Set Expansion to the $2\to q$ norm, we can reproduce a similar result to [ABS10].

2 Bounding the value of SoS relaxations

We show that in several cases, the SoS SDP hierarchy gives strong bounds on various instances. At the heart of these results is a general approach of “lifting” proofs about one-dimensional objects into the SoS relaxation domain. Thus we transform the prior proofs that these instances have small objective value, into a proof that the SoS relaxation also has a small objective The crucial observation is that many proofs boil down to the simple fact that a sum of squares of numbers is always non-negative. It turns out that this “sum of squares” axiom is surprisingly powerful (e.g. implying a version of the Cauchy–Schwarz inequality given by Lemma A.4), and many proofs boil down to essentially this principle.

3 The 2-to-4 norm and small-set expansion

Bounds on the $p\to q$ norm of operators for $p<q$ have been used to show fast convergence of Markov chains. In particular, it is known that if the projector to the top eigenspace of a graph $G$ has bounded $2\to 4$ norm, then that graph is a small-set expander in the sense that sets of $o(1)$ fraction of the vertices have most of their edges exit the set. In this work we show a converse to this statement, proving that if $G$ is a small-set expander, then the corresponding projector has bounded $2\to 4$ norm. As mentioned above, one corollary of this result is that a good (i.e., dimension-independent) approximation to the $2\to 4$ norm will refute the Small-Set Expansion hypothesis of [RS10].

We give a rough sketch of the proof. Suppose that $G$ is a sufficiently strong small-set expander, in the sense that every set $S$ with $|S|\leqslant\delta|V(G)|$ has all but a tiny fraction of the edges $(u,v)$ with $u\in S$ satisfying $v\not\in S$. Let $f$ be a function in the eigenspace of $G$ corresponding to eigenvalues larger than, say $0.99$. Since $f$ is in the top eigenspace, for the purposes of this sketch let’s imagine that it satisfies

where the expectation is over a random neighbor $y$ of $x$. Now, suppose that $\operatorname*{\varmathbb{E}}f(x)^{2}=1$ but $\operatorname*{\varmathbb{E}}f(x)^{4}=C$ for some $C\gg\operatorname{poly}(1/\delta)$. That means that most of the contribution to the $4$-norm comes from the set $S$ of vertices $x$ such that $f(x)\geqslant(1/2)C^{1/4}$, but $|S|\ll\delta|V(G)|$. Moreover, suppose for simplicity that $f(x)\in((1/2)C^{1/4},2C^{1/4})$, in which case the condition (*) together with the small-set expansion condition that for most vertices $y$ in $\Gamma(S)$ (the neighborhood of $S$) satisfy $f(y)\geqslant C^{1/4}/3$, but the small-set expansion condition, together with the regularity of the graph imply that $|\Gamma(S)|\geqslant 200|S|$ (say), which implies that $\operatorname*{\varmathbb{E}}f(x)^{4}\geqslant 2C$—a contradiction.

The actual proof is more complicated, since we can’t assume the condition (4.1). Instead we will approximate it it by assuming that $f$ is the function in the top eigenspace that maximizes the ratio $\lVert f\rVert_{4}/\lVert f\rVert_{2}$. See Section 8 for the details.

4 The 2-to-4 norm and the injective tensor norm

To relate the $2\to 4$ norm to the injective tensor norm, we start by establishing equivalences between the $2\rightarrow 4$ norm and a variety of different tensor problems. Some of these are straightforward exercises in linear algebra, analogous to proving that the largest eigenvalue of $M^{T}M$ equals the square of the operator norm of $M$.

One technically challenging reduction is between the problem of optimizing a general degree-4 polynomial $f(x)$ for $x\in\varmathbb R^{n}$ and a polynomial that can be written as the sum of fourth powers of linear functions of $x$. Straightforward approaches will magnify errors by $\operatorname{poly}(n)$ factors, which would make it impossible to rule out a PTAS for the $2\rightarrow 4$ norm. This would still be enough to prove that a $1/\operatorname{poly}(n)$ additive approximation is NP-hard. However, to handle constant-factor approximations, we will instead use a variant of a reduction in [HM10]. This will allow us to map a general tensor optimization problem (corresponding to a general degree-4 polynomial) to a $2\rightarrow 4$ norm calculation without losing very much precision.

To understand this reduction, we first introduce the $n^{2}\times n^{2}$ matrix $A_{2,2}$ (defined in Section 9) with the property that $\|A\|_{2\rightarrow 4}^{4}=\max z^{T}A_{2,2}z$, where the maximum is taken over unit vectors $z$ that can be written in the form $x\otimes y$. Without this last restriction, the maximum would simply be the operator norm of $A_{2,2}$. Operationally, we can think of $A_{2,2}$ as a quantum measurement operator, and vectors of the form $x\otimes y$ as unentangled states (equivalently we say that vectors in this form are tensor product states, or simply “product states”). Thus the difference between $\|A\|_{2\rightarrow 4}^{4}$ and $\|A_{2,2}\|_{2\rightarrow 2}^{2}$ can be thought of as the extent to which the measurement $A_{2,2}$ can notice the difference between product states and (some) entangled state.

Next, we define a matrix $A^{\prime}$ whose rows are of the form $(x^{\prime}\otimes y^{\prime})^{*}\sqrt{A_{2,2}}$, where $x^{\prime},y^{\prime}\in\varmathbb R^{n}$ range over a distribution that approximates the uniform distribution. If $A^{\prime}$ acts on a vector of the form $x\otimes y$, then the maximum output 4-norm (over $L_{2}$-unit vectors $x,y$) is precisely $\|A\|_{2\rightarrow 4}$. Intuitively, if $A^{\prime}$ acts on a highly “entangled” vector $z$, meaning that $\langle z,x\otimes y\rangle$ is small for all unit vectors $x,y$, then $\|A^{\prime}z\|_{4}$ should be small. This is because $z$ will have small overlap with $x^{\prime}\otimes y^{\prime}$, and $A_{2,2}$ is positive semi-definite, so its off-diagonal entries can be upper-bounded in terms of its operator norm. These arguments (detailed in Section 9.2) lead to only modest bounds on $A^{\prime}$, but then we can use an amplification argument to make the $2\rightarrow 4$ norm of $A^{\prime}$ depend more sensitively on that of $A$, at the cost of blowing up the dimension by a polynomial factor.

The reductions we achieve also permit us, in Section 9.3, to relate our Tensor-SDP algorithm with the sum-of-squares relaxation used by Doherty, Parrilo, and Spedalieri [DPS04] (henceforth DPS). We show the two relaxations are essentially equivalent, allowing us to import results proved, in some cases, with techniques from quantum information theory. One such result, from [BaCY11], requires relating $A_{2,2}$ to a quantum measurement of the 1-LOCC form. This means that there are two $n$-dimensional subsystems, combined via tensor products, and $A_{2,2}$ can be implemented as a measurement on the first subsystem followed by a measurement on the second subsystem that is chosen conditioned on the results of the first measurement. The main result of [BaCY11] proved that such 1-LOCC measurements exhibit much better behavior under DPS, and they obtain nontrivial approximation guarantees with only $O(\log(n)/\varepsilon^{2})$ rounds. Since this is achieved by DPS, it also implies an upper bound on the error of Tensor-SDP. This upper bound is $\varepsilon Z$, where $Z$ is the smallest number for which $A_{2,2}\leqslant ZM$ for some 1-LOCC measurement $M$. While $Z$ is not believed to be efficiently computable, it is at least $\|A_{2,2}\|_{2\rightarrow 2}$, since any measurement $M$ has $\|M\|_{2\rightarrow 2}\leqslant 1$. To upper bound $Z$, we can explicitly construct $A_{2,2}$ as a quantum measurement. This is done by the following protocol. Let $a_{1},\ldots,a_{m}$ be the rows of $A$. One party performs the quantum measurement with outcomes $\{\alpha a_{i}a_{i}^{T}\}_{i=1}^{m}$ (where $\alpha$ is a normalization factor) and transmits the outcome $i$ to the other party. Upon receiving message $i$, the second party does the two outcome measurement $\{\beta a_{i}a_{i}^{T},I-\beta a_{i}a_{i}^{T}\}$ and outputs 0 or 1 accordingly, where $\beta$ is another normalization factor. The measurement $A_{2,2}$ corresponds to the “0” outcomes. For this to be a physically realizable 1-LOCC measurement, we need $\alpha\leqslant\|A^{T}A\|_{2\rightarrow 2}$ and $\beta\leqslant\|A\|_{2\rightarrow\infty}^{2}$. Combining these ingredients, we obtain the approximation guarantee in Theorem 2.3. More details on this argument are in Section 9.3.1.

5 Definitions and Notation

In most of this paper we use expectation norms defined as above, but in some contexts the counting norms will be more convenient. We will usually stick to the convention that functions use expectation norms while vectors use the counting norms. For a vector $v\in\varmathbb C^{\mathcal{U}}$ and $p\geqslant 1$, the $p$ counting norm of $v$, denoted ${\boldsymbol{\lVert}}v{\boldsymbol{\rVert}}_{p}$, is defined to be $\left(\sum_{i\in\mathcal{U}}|v_{i}|^{p}\right)^{1/p}$. The counting inner product of two vectors $u,v\in\varmathbb R^{\mathcal{U}}$, denoted as $\boldsymbol{\langle}u,v\boldsymbol{\rangle}$, is defined to be $\sum_{i\in\mathcal{U}}u_{i}v_{i}^{*}$.

The Tensor-SDP algorithm

There is a very natural SoS program for the $2\to 4$ norm for a given linear operator $A\colon L_{2}(\mathcal{U})\to L_{2}(\mathcal{V})$:

Note that $\lVert Af\rVert_{4}^{4}$ is indeed a degree $4$ polynomial in the variables $\{f(u)\}_{u\in\mathcal{U}}$. The $\textup{{Tensor-SDP}}^{(d)}$ algorithm makes sense for $d\geqslant 4$, and we denote by Tensor-SDP its most basic version where $d=4$. The Tensor-SDP algorithm applies not just to the $2\to 4$ norm, but to optimizing general polynomials over the unit ball of $L_{2}(\mathcal{U})$ by replacing $\lVert Af\rVert_{4}^{4}$ with an arbitrary polynomial $P$.

While we do not know the worst-case performance of the Tensor-SDP algorithm, we do know that it performs well on random instances (see Section 7), and (perhaps more relevant to the UGC) on the projector to low-degree polynomials (see Theorem 2.2). The latter is a corollary of the following result:

Over the space of $n$-variate Fourier polynomialsAn $n$-variate Fourier polynomial with degree at most $d$ is a function $f\colon\{\pm 1\}^{n}\to\varmathbb R$ of the form $f=\sum_{\alpha\subseteq[n],|\alpha|\leqslant d}\hat{f}_{\alpha}\chi_{\alpha}$ where $\chi_{\alpha}(x)=\prod_{i\in\alpha}x_{i}$. $f$ with degree at most $d$,

where the expectations are over $\{\pm 1\}^{n}$.

The result is proven by a careful variant of the standard inductive proof of the hypercontractivity for low-degree polynomials (see e.g. [O’D07]). We include it in this part of the paper since it is the simplest example of how to “lift” known proofs about functions over the reals into proofs about the fictitious random variables that arise in semidefinite programming hierarchies. To strengthen the inductive hypothesis, we will prove the more general statement that for $f$ and $g$ being $n$-variate Fourier polynomials with degrees at most $d$ and $e$, it holds that $\operatorname*{\varmathbb{E}}f^{2}g^{2}\preceq 9^{\frac{d+e}{2}}\left(\operatorname*{\varmathbb{E}}f^{2}\right)\left(\operatorname*{\varmathbb{E}}g^{2}\right)$. (Formally, this polynomial relation is over the linear space of pairs of $n$-variate Fourier polynomials $(f,g)$, where $f$ has degree at most $d$ and $g$ has degree at most $e$.) The proof is by induction on the number of variables.

If one of the functions is constant (so that $d=0$ or $e=0$), then $\operatorname*{\varmathbb{E}}f^{2}g^{2}=(\operatorname*{\varmathbb{E}}f^{2})(\operatorname*{\varmathbb{E}}g^{2})$, as desired. Otherwise, let $f_{0},f_{1},g_{0},g_{1}$ be Fourier polynomials depending only on $x_{1},\ldots,x_{n-1}$ such that $f(x)=f_{0}(x)+x_{n}f_{1}(x)$ and $g(x)=g_{0}(x)+x_{n}g_{1}(x)$. The Fourier polynomials $f_{0},f_{1},g_{0},g_{1}$ depend linearly on $f$ and $g$ (because $f_{0}(x)=\tfrac{1}{2}f(x_{1},\ldots,x_{n-1},1)+\tfrac{1}{2}f(x_{1},\ldots,x_{n-1},-1)$ and $f_{1}(x)=\tfrac{1}{2}f(x_{1},\ldots,x_{n-1},1)-\tfrac{1}{2}f(x_{1},\ldots,x_{n-1},-1)$). Furthermore, the degrees of $f_{0}$, $f_{1}$, $g_{0}$, and $g_{1}$ are at most $d$, $d-1$, $e$, and $e-1$, respectively.

Since $\operatorname*{\varmathbb{E}}x_{n}=\operatorname*{\varmathbb{E}}x_{n}^{3}=0$, if we expand $\operatorname*{\varmathbb{E}}f^{2}g^{2}=\operatorname*{\varmathbb{E}}(f_{0}+x_{n}f_{1})^{2}(g_{0}+x_{n}g_{1})^{2}$ then the terms where $x_{n}$ appears in an odd power vanish, and we obtain

By expanding the square expression $2\operatorname*{\varmathbb{E}}(f_{0}f_{1}-g_{0}g_{1})^{2}$, we get $4\operatorname*{\varmathbb{E}}f_{0}f_{1}g_{0}g_{1}\preceq 2\operatorname*{\varmathbb{E}}f_{0}^{2}g_{1}^{2}+f_{1}^{2}g_{0}^{2}$ and thus

Applying the induction hypothesis to all four terms on the right-hand side of (5.1) (using for the last two terms that the degree of $f_{1}$ and $g_{1}$ is at most $d-1$ and $e-1$),

Since $\operatorname*{\varmathbb{E}}f_{0}^{2}+\operatorname*{\varmathbb{E}}f_{1}^{2}=\operatorname*{\varmathbb{E}}(f_{0}+x_{n}f_{1})^{2}=\operatorname*{\varmathbb{E}}f^{2}$ (using $\operatorname*{\varmathbb{E}}x_{n}=0$) and similarly $\operatorname*{\varmathbb{E}}g_{0}^{2}+\operatorname*{\varmathbb{E}}g_{1}^{2}=\operatorname*{\varmathbb{E}}g^{2}$, we derive the desired relation $\operatorname*{\varmathbb{E}}f^{2}g^{2}\preceq 9^{\frac{d+e}{2}}\left(\operatorname*{\varmathbb{E}}f^{2}\right)\left(\operatorname*{\varmathbb{E}}g^{2}\right)$. ∎

SoS succeeds on Unique Games integrality gaps

In this section we prove Theorem 2.6, showing that 8 rounds of the SoS hierarchy can beat the Basic SDP program on the canonical integrality gaps considered in the literature.

For sufficiently small $\varepsilon$ and large $k$, and every $n\in\varmathbb N$, let $\mathcal{W}$ be an $n$-variable $k$-alphabet Unique Games instance of the type considered in [RS09, KS09, KPS10] obtained by composing the “quotient noisy cube” instance of [KV05] with the long-code alphabet reduction of [KKMO04] so that the best assignment to $\mathcal{W}$’s variable satisfies at most an $\varepsilon$ fraction of the constraints. Then, on input $\mathcal{W}$, eight rounds of the SoS relaxation outputs at most $1/100$.

The proof is very technical, as it is obtained by taking the already rather technical proofs of soundness for these instances, and “lifting” each step into the SoS hierarchy, a procedure that causes additional difficulties. The high level structure of all integrality gap instances constructed in the literature was the following: Start with a basic integrality gap instance of Unique Games where the Basic SDP outputs $1-o(1)$ but the true optimum is $o(1)$, the alphabet size of $\mathcal{U}$ is (necessarily) $R=\omega(1)$. Then, apply an alphabet-reduction gadget (such as the long code, or in the recent work [BGH+11] the so called “short code”) to transform $\mathcal{U}$ into an instance $\mathcal{W}$ with some constant alphabet size $k$. The soundness proof of the gadget guarantees that the true optimum of $\mathcal{U}$ is small, while the analysis of previous works managed to “lift” the completeness proofs, and argue that the instance $\mathcal{U}$ survives a number of rounds that tends to infinity as $\varepsilon$ tends to zero, where $(1-\varepsilon)$ is the completeness value in the gap constructions, and exact tradeoff between number of rounds and $\varepsilon$ depends on the paper and hierarchy.

The fact that the basic instance $\mathcal{U}$ has small integral value can be shown by appealing to hypercontractivity of low-degree polynomials, and hence can be “lifted” to the SoS world via Lemma 5.1. The bulk of the technical work is in lifting the soundness proof of the gadget. On a high level this proof involves the following components: (1) The invariance principle of [MOO05], saying that low influence functions cannot distinguish between the cube and the sphere; this allows us to argue that functions that perform well on the gadget must have an influential variable, and (2) the influence decoding procedure of [KKMO04] that maps these influential functions on each local gadget into a good global assignment for the original instance $\mathcal{U}$.

The invariance principle poses a special challenge, since the proof of [MOO05] uses so called “bump” functions which are not at all low-degree polynomials.A similar, though not identical, challenge arises in [BGH+11] where they need to extend the invariance principle to the “short code” setting. However, their solution does not seem to apply in our case, and we use a different approach. We use a weaker invariance principle, only showing that the $4$ norm of a low influence function remains the same between two probability spaces that agree on the first $2$ moments. Unlike the usual invariance principle, we do not move between Bernoulli variables and Gaussian space, but rather between two different distributions on the discrete cube. It turns out that for the purposes of these Unique Games integrality gaps, the above suffices. The lifted invariance principle is proven via a “hybrid” argument similar to the argument of [MOO05], where hypercontractivity of low-degree polynomials again plays an important role.

The soundness analysis of [KKMO04] is obtained by replacing each local function with an average over its neighbors, and then choosing a random influential coordinate from the new local function as an assignment for the original uniquegames instance. We follow the same approach, though even simple tasks such as independent randomized rounding turn out to be much subtler in the lifted setting. However, it turns out that by making appropriate modification to the analysis, it can be lifted to complete the proof of Theorem 2.6.

We now turn to the actual proof of Theorem 6.1. The proof consists of lifting to the SoS hierarchy all the steps used in the analysis of previous integrality gaps, which themselves arise from hardness reductions. We start in Section 6.2 by showing a sum-of-squares proof for a weaker version of [MOO05]’s invariance principle. Then in Section 6.3 we show how one can perform independent rounding in the SoS world (this is a trivial step in proofs involving true random variables, but becomes much more subtle when dealing with SoS solutions). In Sections 6.4 and 6.5 we lift variants of the [KKMO04] dictatorship test. The proof uses a SoS variant of influence decoding, which is covered in Section 6.6. Together all these sections establish SoS analogs of the soundness properties of the hardness reduction used in the previous results. Then, in Section 6.7 we show that analysis of the basic instance has a sum of squares proof (since it is based on hypercontractivity of low-degree polynomials). Finally in Section 6.8 we combine all these tools to conclude the proof. In Section 6.9 we discuss why this proof applies (with some modifications) also to the “short-code” based instances of [BGH+11].

2 Invariance Principle for Fourth Moment

In this section, we will give a sum-of-squares proof for a variant of the invariance principle of [MOO05]. Instead of for general smooth functionals (usually constructed from “bump functions”), we show invariance only for the fourth moment. It turns out that invariance of the fourth moment is enough for our applications.

Let $k=2^{t}$ for $t\in\varmathbb N$ and let $\mathcal{X}=(\mathcal{X}_{1},\ldots,\mathcal{X}_{R})$ be an independent sequenceAn orthonormal ensemble is a collection of orthonormal real-valued random variables, one being the constant $1$. A sequence of such ensembles is independent if each ensemble is defined over an independent probability space. (See [MOO05] for details.) of orthonormal ensembles $\mathcal{X}_{r}=(X_{r,0},\ldots,X_{r,k-1})$. Concretely, we choose $X_{r,i}=\chi_{i}(x_{r})$, where ${\chi_{0},\ldots,\chi_{k-1}}$ is the set of characters of $\varmathbb F_{2}^{t}$ and $x$ is sampled uniformly from $(\varmathbb F_{2}^{t})^{R}$. Every random variable over $(\varmathbb F_{2}^{t})^{R}$ can be expressed as a multilinear polynomial over the sequence $\mathcal{X}$. In this sense, $\mathcal{X}$ is maximally dependent. On the other hand, let $\mathcal{Y}=(\mathcal{Y}_{1},\ldots,\mathcal{Y}_{R})$ be a sequence of ensembles $\mathcal{Y}_{r}=(Y_{r,0},\ldots,Y_{r,k-1})$, where $Y_{r,0}\equiv 1$ and $Y_{r,j}$ are independent, unbiased $\{\pm 1\}$ Bernoulli variables. The sequence $\mathcal{Y}$ is maximally independent since it consists of completely independent random variables.

(Since the expressions $\operatorname*{\varmathbb{E}}_{\mathcal{X}}f^{4}$ and $\operatorname*{\varmathbb{E}}_{\mathcal{Y}}f^{4}$ are degree-$4$ polynomials in $f$, their pseudo-expectations are defined.)

We consider the following intermediate sequences of ensembles $\mathcal{Z}^{(r)}=(\mathcal{X}_{1},\ldots,\mathcal{X}_{r},\mathcal{Y}_{r+1},\ldots,\mathcal{Y}_{R})$. Note that $\mathcal{Z}^{(0)}=\mathcal{Y}$ and $\mathcal{Z}^{(R)}=\mathcal{X}$. For $r\in\varmathbb N$, we write $f=E_{r}f+D_{r}f$, where $E_{r}f$ is the part of $f$ that does not dependent on coordinate $r$ and $D_{r}f=f-E_{r}f$. For all $r\in\varmathbb N$, the following identities (between polynomials in $f$) hold

The last step uses that the first two moments of the ensembles $\mathcal{X}_{r}$ and $\mathcal{Y}_{r}$ match and that $E_{r}f$ does not dependent on coordinate $r$.

Next, we consider the term $\sum_{r}\operatorname*{\varmathbb{E}}_{\mathcal{Z}^{(r)}}(E_{r}f)(D_{r}f)^{3}$. (The remaining two terms are analogous.) To bound its pseudo-expectation, we apply Cauchy-Schwarz,

3 Interlude: Independent Rounding

In this section, we will show how to convert variables that satisfy $f^{2}\preceq f$ to variables $\bar{f}$ satisfying $\bar{f}^{2}=\bar{f}$. The derived variables $\bar{f}$ will inherit several properties of the original variables $f$ (in particular, multilinear expectations). This construction corresponds to the standard independent rounding for variables with values between and $1$. The main challenge is that our random variables are fictitious.

Let $f$ be a $4$-f.r.v. over $\varmathbb R^{n}$. Suppose $f_{i}^{2}\preceq f_{i}$ (in terms of an unspecified jointly-distributed $4$-f.r.v.). Note that for real numbers $x$, the condition $x^{2}\leqslant x$ is equivalent to $x\in$.

4 Dictatorship Test for Small-Set Expansion

Let $\Omega=\{0,\ldots,k-1\}$ and let $T_{1-\varepsilon}$ be the noise graph on $\Omega^{R}$ with second largest eigenvalue $1-\varepsilon$. Let $f$ be a $4$-f.r.v. over $L_{2}(\Omega^{R})$. Suppose $f^{2}\preceq f$ (in terms of an unspecified jointly-distributed $4$-f.r.v.). Note that for real numbers $x$, the condition $x^{2}\leqslant x$ is equivalent to $x\in$.

The following theorem is an analog of the “Majority is Stablest” result [MOO05].

(Here, we assume that $\varepsilon$, $\delta$ and $\tau$ are sufficiently small.)

The previous theorem is about graph expansion (measured by the quadratic form $\langle f,T_{1-\varepsilon}f\rangle$). The following lemma allows us to relate graph expansion to the $4$-norm of the projection of $f$ into the span of the eigenfunctions of $T_{1-\varepsilon}$ with significant eigenvalue. We will be able to bound this $4$-norm in terms of the influences of $f$ (using the invariance principle in the previous section).

Let $f$ be a $4$-f.r.v. over $L_{2}(\Omega^{R})$. Suppose $f^{2}\preceq f$ (in terms of unspecified jointly-distributed $4$-f.r.v. s). Then for all $\lambda>0$,

Here, $P_{>\lambda}$ is the projector into the span of the eigenfunctions of $T_{1-\varepsilon}$ with eigenvalue larger than $\lambda$.

The following relation between polynomials holds

By Corollary 6.5, there exists a $4$-f.r.v. $(f,\bar{f})$ over $L_{2}(\Omega^{R})\times L_{2}(\Omega^{R})$ such that $\bar{f}^{2}\equiv_{\bar{f}}\bar{f}$. Then,

To balance the terms $(1/\lambda)^{O(1/\varepsilon)}\delta^{5/4}$ and $\lambda\delta$, we choose $\lambda=\delta^{\Omega(\varepsilon)}$. We conclude the desired bound,

5 Dictatorship Test for Unique Games

Let $\Omega=\varmathbb Z_{k}$ (cyclic group of order $k$) and let $f$ be a $4$-f.r.v. over $L_{2}(\Omega\times\Omega^{R})$. Here, $f(a,x)$ is intended to be $0/1$ variable indicating whether symbol $a$ is assigned to the point $x$.

The following graph $T^{\prime}_{1-\varepsilon}$ on $\Omega\times\Omega^{R}$ corresponds to the $2$-query dictatorship test for Unique Games [KKMO04],

Here, $y\sim_{1-\varepsilon}x$ means that $y$ is a random neighbor of $x$ in the graph $T_{1-\varepsilon}$ (the $\varepsilon$-noise graph on $\Omega^{R}$).

We define $\bar{f}(x)\mathrel{\mathop{:}}=\operatorname*{\varmathbb{E}}_{c\in\Omega}f(c,x-c\cdot\varmathbb I)$. (We think of $\bar{f}$ as a variable over $L_{2}(\Omega^{R})$.) Then, the following polynomial identity (in $f$) holds

(Here, we assume that $\varepsilon$, $\delta$ and $\tau$ are sufficiently small.)

6 Influence Decoding

Let $\mathcal{U}$ be a unique game with vertex set $V$ and alphabet $[R]$. Recall that we represent $\mathcal{U}$ as a distribution over triples $(u,v,\pi)$ where $u,v\in V$ and $\pi$ is a permutation of $[R]$. The triples encode the constraints of $\mathcal{U}$. We assume that the unique game $\mathcal{U}$ is regular in the same that every vertex participates in the same fraction of constraints.

Let $\Omega=\varmathbb Z_{k}$ (cyclic group of order $k$). We reduce $\mathcal{U}$ to a unique game $\mathcal{W}=\mathcal{W}_{\varepsilon,k}(\mathcal{U})$ with vertex set $V\times\Omega^{R}$ and alphabet $\Omega$. Let $f=\{f_{u}\}_{u\in V}$ be a variable over $L_{2}(\Omega\times\Omega^{R})^{V}$. The unique game $\mathcal{W}$ corresponds to the following quadratic form in $f$,

Here, $(u,v,\pi)\sim\mathcal{U}\mid u$ denotes a random constraint of $\mathcal{U}$ incident to vertex $u$, the graph $T^{\prime}_{1-\varepsilon}$ corresponds to the dictatorship test of Unique Games defined in Section 6.5, and $f^{(\pi)}_{v}(a,x)=f_{v}(a,\pi.x)$ is the function obtained by permuting the last $R$ coordinates according to $\pi$ (where $\pi.x(i)=x_{\pi(i)}$).

We define $g_{u}=\operatorname*{\varmathbb{E}}_{(u,v,\pi)\sim\mathcal{U}\mid u}f^{(\pi)}_{v}$. Then,

By applying Theorem 6.8 to (6.2), we can bound the objective value of $f$

The arguments in this subsection imply the following theorem.

The optimal value of the level-$d$ SoS relaxation for the unique game $\mathcal{W}=\mathcal{W}_{\varepsilon,k}(\mathcal{U})$ is bounded from above by

Since the quadratic form $\lVert G_{\mathcal{U}}h\rVert^{2}$ has only nonnegative coefficients (in the standard basis), we can use Corollary 6.5 to ensure that the level-$d/2$ random variable $h$ satisfies in addition $h^{2}\equiv_{h}h$.

7 Certifying Small-Set Expansion

Let $T_{1-\varepsilon}$ be a the noise graph on $\{\pm 1\}^{R}$ with second largest eigenvalue $1-\varepsilon$.

By Lemma 6.7 (applying it for the case $\Omega=\{0,1\}$), for every $\lambda>0$,

To balance the terms, we choose $\lambda=\delta^{\Omega(\varepsilon)}$, which gives the desired bound. ∎

8 Putting Things Together

Let $T_{1-\eta}$ be a the noise graph on $\{\pm 1\}^{R}$ with second largest eigenvalue $1-\eta$. Let $\mathcal{U}=\mathcal{U}_{\eta,R}$ be an instance of Unique Games with label-extended graph $G_{\mathcal{U}}=T_{1-\eta}$ (e.g., the construction in [KV05]).

Combining Theorem 6.9 (with $d=4$) and Theorem 6.11 gives the following result.

The optimal value of the level-$8$ SoS relaxation for the unique game $\mathcal{W}=\mathcal{W}_{\varepsilon,k}(\mathcal{U}_{\eta,R})$ is bounded from above by

In particular, the optimal value of the relaxation is close to $1/k^{\Omega(\varepsilon)}$ if $\log R\gg(\log k)^{2}/\eta$.

9 Refuting Instances based on Short Code

Let $\mathcal{U}^{\prime}=\mathcal{U}^{\prime}_{\eta,R}$ be an instance of Unique Games according to the basic construction in [BGH+11]. (The label-extended graph of $\mathcal{U}$ will be a subgraph of $T_{1-\varepsilon}$ induced by the subset of $\{\pm 1\}^{R}$ corresponding to a Reed–Muller code, that is, evaluations of low-degree $\varmathbb F_{2}$-polynomials.)

Let $\mathcal{W}^{\prime}=\mathcal{W}^{\prime}_{\varepsilon,k}(\mathcal{U}^{\prime}_{\eta,R})$ be the unique game obtained by applying the short-code alphabet reduction of [BGH+11].

The following analog of Theorem 6.12 holds.

The optimal value of the level-$8$ SoS relaxation for the unique game $\mathcal{W}^{\prime}=\mathcal{W}^{\prime}_{\varepsilon,k}(\mathcal{U}^{\prime}_{\eta,R})$ is bounded from above by

In particular, the optimal value of the relaxation is close to $1/k^{\Omega(\varepsilon)}$ if $\log R\gg(\log k)^{2}/\eta$.

The proof of Theorem 6.13 is almost literally the same as the proof of Theorem 6.12. In the following, we sketch the main arguments why the proof doesn’t have to change. First, several of the results of the previous sections apply to general graphs and instances of Unique Games. In particular, Lemma 6.7 applies to general graphs and Theorem 6.9 applies to general gadget-composed instances of unique games assuming a “Majority is Stablest” result for the gadget. In fact, the only parts that require further justification are the invariance principle (Theorem 6.2) and hypercontractivity bound (Lemma 5.1). Both the invariance principle and the hypercontractivity bound are about the fourth moment of a low-degree Fourier polynomial (whose coefficients are fictitious random variables). For the construction of [BGH+11], we need to argue about the fourth moment with respect to a different distribution over inputs. (Instead of the uniform distribution, [BGH+11] considers a distribution over inputs related to the Reed–Muller code.) However, this distribution happens to be $k$-wise independent for $k/4$ larger than the degree of our Fourier polynomial. Hence, as a degree-$4$ polynomial in Fourier coefficients, the fourth moment with respect to the [BGH+11]-input distribution is the same as with respect to the uniform distribution, which considered here.