Lower bounds on the size of semidefinite programming relaxations

Introduction

Convex characterizations and relaxations of combinatorial problems have been a consistent, powerful theme in the theory of algorithms since its inception. Linear and semidefinite programming relaxations have been particularly useful for the efficient computation of approximate solutions to NP-hard problems (see, for instance, the books [WS11, Vaz01]). In some sense, semidefinite programs (SDPs) can be seen as combining the rich expressiveness of linear programs with the global geometric power of spectral methods. For many fundamental combinatorial problems, this provides a genuinely new structural and computational perspective [GW95, KMS98, ARV09]. Indeed, for an array of optimization problems, the best-known approximation algorithms can only be achieved via SDP relaxations.

It has long been known that integrality gaps for linear programs (LPs) can often lead to gadgets for NP-hardness of approximation reductions (see, e.g., [LY93, CGH+05, HK03]). Furthermore, assuming the Unique Games Conjecture [Kho02], it is known that integrality gaps for SDPs can be translated directly into hardness of approximation results [KKMO04, Aus10, Rag08]. All of this suggests that the computational model underlying LPs and SDPs is remarkably powerful.

In the setting of linear programs (LPs), the search for a model and characterization began in a remarkable work of Yannakakis [Yan91]. He proved that the TSP and matching polytopes do not admit symmetric linear programming formulations of size $2^{o(n)}$, where $n$ is the number of vertices in the underlying graph. In the process, he laid the structural framework (in terms of nonnegative factorizations) that would underlie all future work in the subject. It took over 20 years before Fiorini, Massar, Pokutta, Tiwary, and de Wolf [FMP+12] were able to remove the symmetry assumption and obtain a lower bound of $2^{\Omega(\sqrt{n})}$ on the size of any LP formulation. Soon afterward, Rothvoß [Rot14] gave a lower bound of $2^{\Omega(n)}$ on the size of any LP formulation for the matching polytope (and also TSP), completing Yannakakis’ vision.

Despite the progress in understanding the power of LP formulations, it remained a mystery whether there were similar strong lower bounds in the setting of SDPs. An analogous positive semidefinite factorization framework was provided in [FMP+12, GPT11]. Following the LP methods of [CLRS13], the papers [LRST14, FSP13] proved exponential lower bounds on the size of symmetric SDP formulations for NP-hard constraint satisfaction problems (CSPs).

In the present work, we prove strong lower bounds on the size of general SDP formulations for the cut, TSP, and stable set polytopes. Moreover, we show that polynomial-size SDP relaxations cannot achieve arbitrarily good approximations for many NP-hard constraint satisfaction problems. For instance, no polynomial-size family of relaxations can achieve better than a $7/8$-approximation for max 3-sat. More generally, we show that the low-degree sum-of-squares SDP relaxations yield the best approximation among all polynomial-sized families of relaxations for max-CSPs.

This is achieved by relating arbitrary SDP formulations to those coming from the sum-of-squares SDP hierarchyThis hierarchy is also frequently referred to as the Lasserre SDP hierarchy. [Las01, Par00, Sho87], analogous to our previous work with Chan relating LP formulations to the Sherali–Adams hierarchy [CLRS13]. The SDP setting poses a number of significant challenges. At a very high level, our approach can be summarized as follows: Given an arbitrary SDP formulation of small size, we use methods from quantum entropy maximization and online convex optimization (often going by the name “matrix multiplicative weights update”) to learn an approximate low-degree sum-of-squares formulation on a subset of the input variables. In the next section, we present a formal overview of our results, and a discussion of the connections to quantum information theory, real algebraic geometry, and proof complexity.

The results of this work fall along two broad themes, lower bounds on spectrahedral lifts of specific polytopes and lower bounds on SDP relaxations for constraint satisfaction problems. Both sets of results are consequences of a general method for proving lower bounds on positive semidefinite rank. For the convenience of the reader, we have organized the two themes in two self-contained trajectories. Thus, lower bounds on spectrahedral lifts can be accessed via Section 1.1, Section 1.3, Section 2, Section 3 and Section 5. The lower bounds for constraint satisfaction problems can be reached through Section 1.2, Section 1.3, Section 2, Section 3 and Section 6.

We also present general results on approximating density operators against families of linear tests through quantum learning in Section 4. Finally, in Section 7, we exhibit applications of our techniques to non-negative rank; in particular, this is used to give a simple, self-contained proof of a lower bound on the nonnegative rank of the unique disjointness matrix.

1 Spectrahedral lifts of polytopes

one says that $P$ admits a positive-semidefinite (psd) lift of size $k$. (This terminology is taken from [FGP+14].) We remark that the intersection of a PSD cone with an affine subspace is often referred to as a spectrahedron.

Here, the optimization problem on the right is a semidefinite programming problem in $k$-by-$k$ matrices. This idea also goes under the name of a semidefinite extended formulation [FMP+12].

In Section 5.1, we show the following strong lower bound on its psd rank.

The importance of the correlation polytope $\text{{{corr}}}_{n}$ lies in the fact that a number of interesting polytopes from combinatorial optimization contain a face that linearly projects to $\text{{{corr}}}_{n}$ . We first define a few different families of polytopes and then recall their relation to $\text{{{corr}}}_{n}$.

Finally, consider an arbitrary $n$-vertex graph $G=([n],E)$. We recall that a subset of vertices $S\subseteq[n]$ is an independent set (also called a stable set) if there are no edges between vertices in $S$. The stable set polytope of $G$ is given by

By results of [DS90] and [FMP+12] (see Proposition 5.2), Theorem 1.1 directly implies the following lower bounds on the psd rank of the cut, TSP, and stable set polytopes.

The following lower bounds hold for every $n\geqslant 1$,

2 Semidefinite relaxations and constraint satisfaction

We now formalize a computational model of semidefinite relaxations for combinatorial optimization problems and prove strong lower bounds for it. Unlike the polytope setting in the previous section, this model also allows us to capture approximation algorithms directly.

Many basic optimization problems are special cases of this general problem, corresponding to functions $f$ of a particular form: For the problem of finding the maximum cut in a graph $G$ with $n$ vertices, the function $f$ outputs on input $x\in\{0,1\}^{n}$ the number of edges in $G$ that cross the bipartition represented by $x$, i.e., $f(x)$ is the number of edges $\{i,j\}\in E(G)$ with $x_{i}\neq x_{j}$. Similarly, for max 3-sat on a 3CNF formula $\varphi$ with $n$ variables, $f(x)$ is the number of clauses in $\varphi$ satisfied by the assignment $x$. More generally, for any $k$-ary boolean constraint satisfaction problem, the function $f$ counts the number of satisfied constraints. Note that in these examples, the functions have at most degree $2$, degree $3$, and degree $k$, respectively.

The $\overline{\textup{sos}}_{d}$ upper bound is equivalent to the degree-$d$ sum-of-squares (also known as the level-$d/2$ Lasserre) SDP bound, and for small values of $d$, these upper bounds underlie the best-known approximation algorithms for several optimization problems. For example, the Goemans–Williamson algorithm for max cut is based on the upper bound $\overline{\textup{sos}}_{2}$. If we let $\alpha_{GW}\approx 0.878$ be the approximation ratio of this algorithm, then every graph $G$ satisfies $\max(f_{G})\geqslant\alpha_{GW}\cdot\overline{\textup{sos}}_{2}(f_{G})$ where the function $f_{G}$ measures cuts in $G$, i.e., $f_{G}(x)\coloneq\sum_{ij\in E(G)}(x_{i}-x_{j})^{2}$.

A natural generalization of low-degree sum-of-squares certificates is obtained by summing squares of functions in a low-dimensional subspace. We can formulate this generalization as a non-uniform model of computation that captures general semidefinite programming relaxations. First, we make the following definition for a subspace of functions.

In this work, we exhibit unconditional lower bounds in this powerful non-uniform model of computation. For example, we show that the max 3-sat problem cannot be approximated to a factor better than $7/8$ using a polynomial-size family of SDP relaxations. Formally, we show the following lower bound for max 3-sat.

there exists a max 3-sat instance $\Im$ on $n$ variables such that $\max(\Im)\leqslant s$ but $\overline{\textup{sos}}_{U}(\Im)=1$ (i.e., $U$ fails to achieve a factor-$s$ approximation for max 3-sat).

Our main result is a characterization of an optimal semidefinite programming relaxation for the class of constraint satisfaction problems among all families of SDP relaxations of similar size. Roughly speaking, we show that the $O(1)$-degree sum-of-squares relaxations are optimal among all polynomial-sized SDP relaxations for constraint satisfaction problems. Towards stating our main result, we define the class of constraint satisfaction problems. For the sake of clarity, we restrict ourselves to boolean constraint satisfaction problems although the results hold in greater generality.

For a finite collection $\mathscr{P}$ of $k$-ary predicates $P\colon\{0,1\}^{k}\to\{0,1\}$, we let max-$\mathscr{P}$ denote the following optimization problem: An instance $\Im$ consists of boolean variables $X_{1},\ldots,X_{n}$ and a collection of $\mathscr{P}$-constraints $P_{1}(X)=1,\ldots,P_{M}(X)=1$ over these variables. A $\mathscr{P}$-constraint is a predicate $P_{0}\colon\{0,1\}^{n}\to\{0,1\}$ such that $P_{0}(X)=P(X_{i_{1}},\ldots,X_{i_{k}})$ for some $P\in\mathscr{P}$ and distinct indices $i_{1},\ldots,i_{k}\in[n]$. The objective is to find an assignment $x\in\{0,1\}^{n}$ that satisfies as many of the constraints as possible, that is, which maximizes

We denote the optimal value of an assignment for $\Im$ as $\operatorname{opt}(\Im)=\max_{x\in\{0,1\}^{n}}\Im(x)$. For example, max cut corresponds to the case where $\mathscr{P}$ consists of the binary inequality predicate. For max 3-sat, $\mathscr{P}$ contains all eight 3-literal disjunctions, e.g., $X_{1}\vee\bar{X}_{2}\vee\bar{X}_{3}$.

In other words, the upper bound $\overline{\textup{sos}}_{U}$ allows us to distinguishIn order to distinguish between the cases $\max(\Im)\leqslant s$ and $\max(\Im)>c$ it is enough to check whether $\Im$ satisfies $\overline{\textup{sos}}_{U}(\Im)\leqslant c$. In the case $\max(\Im)\leqslant s$, we know that $\overline{\textup{sos}}_{U}(\Im)\leqslant c$ by (1.2). On the other hand, in the case $\max(\Im)>c$, we know that $\overline{\textup{sos}}_{U}(\Im)>c$ because $\overline{\textup{sos}}_{U}(\Im)$ is always an upper bound on $\max(\Im)$. between the cases $\max(\Im)\leqslant s$ and $\max(\Im)>c$ for all instances $\Im\in\Pi_{n}$.

We prove the following theorem, which shows that for every boolean CSP, the approximation guarantees obtained by the degree-$d$ sum-of-squares upper bound (also known as the the level-$d/2$ Lasserre SDP relaxation) are optimal among all semidefinite programming relaxations of size at most $n^{cd}$ for some universal constant $c>0$.

The theorem has several immediate concrete consequences for specific boolean CSPs. First, we know that $O(1)$-degree sos upper bounds do not achieve an approximation ratio better than $7/8$ for max 3-sat [Gri01b, Sch08], therefore Theorem 1.6 implies that polynomial-size SDP relaxations for max 3-sat cannot achieve an approximation ratio better than $7/8$. In fact, a quantitatively stronger version of the above theorem yields Theorem 1.5.

3 Positive semidefinite rank and sum-of-squares degree

In order to prove our results on spectrahedral lifts and semidefinite relaxations, the factorization perspective will be essential. In the LP setting, the characterization of polyhedral lifts and LP relaxations in terms of nonnegative factorizations is a significant contribution of Yannakakis [Yan91]. In the SDP setting, the analogous characterization is in terms of positive semidefinite factorizations [FMP+12, GPT11].

Nonnegative factorizations correspond to the special case that the matrices $\{A_{i}\}$ and $\{B_{j}\}$ are restricted to be diagonal. A rank-$r$ nonnegative factorization can equivalently be viewed as a sum of $r$ rank-$1$ nonnegative factorizations (nonnegative rectangles). Indeed, this viewpoint is crucial for all lower bounds on nonnegative factorization. In contrast, rank-$r$ psd factorizations do not seem to admit a good characterization in terms of rank-$1$ psd factorizations. This difference captures one of the main difficulties of proving psd rank lower bounds.

This notion is closely relatedFor the sake of simplicity, we have only defined this notion for functions on the discrete cube. In more general settings, one has to be a bit more careful; we refer to [GV02]. to (a special case of) the Positivstellensatz proof system of Grigoriev and Vorobjov [GV02]. We refer to the surveys [Lau09, BS14] and the introduction of [OZ12] for a review of such proof systems and their relationship to semidefinite programming.

where $S\subseteq[n]$ runs over all subsets of size $m$ and $x\in\{0,1\}^{n}$.

The reader might observe that the matrix in (1.3) looks very similar to the “pattern matrices” defined by Sherstov [She11]. This comparison is not unfounded; some high-level aspects of our proof are quite similar to his. Random restrictions are a powerful tool for analyzing functions over the discrete cube. We refer to [O’D14, Ch. 4] for a discussion of their utility in the context of discrete Fourier analysis. They were also an important tool in the work [CLRS13] on lower bounds for LPs. Accordingly, one hopes that our methods may have additional applications in communication complexity. This would not be surprising, as there is a model of quantum communication that exactly captures psd rank (see [FMP+12]).

Given the preceding proposition, the following result of Grigoriev on the Knapsack tautologies completes our quest for a lower bound.

has $\deg_{\mathsf{sos}}(f)\geqslant m+1$.

Note that since $m/2$ is not an integer, (1.4) is nonnegative for all $x\in\{0,1\}^{m}$. It turns out that in order to prove stronger lower bounds for $\text{{{corr}}}_{n}$, we will require a lower bound on the approximate sos degree of $f$. Thus the Knapsack tautologies (1.4) will be studied carefully in Section 5.1. In Section 2.2, we discuss the proof of Theorem 1.8 in some detail. Then in Section 3, we present a quantitatively stronger theorem and its proof.

Fix now numbers $k,n\geqslant 1$ and a boolean CSP $\Pi$. Fix a pair of constants $0\leqslant s\leqslant c\leqslant 1$. Suppose our goal is to show a lower bound on the size of SDP relaxations that yield a $(c,s)$-approximation on instances of size $n$. It turns out that this task reduces to proving a lower bound on the positive semidefinite rank of an explicit matrix $M$ indexed by problem instances and problem solutions (points on the discrete cube in our case).

For any boolean CSP $\Pi_{n}$ and any constants $0\leqslant s<c\leqslant 1$, let $U$ be a subspace of minimal dimension that achieves a $(c,s)$-approximation for $\Pi_{n}$. Denote the set of instances

Before describing the proof of this proposition, observe that together with our main theorem the proposition implies Theorem 1.6 (optimality of degree-$d$ sum-of-squares for approximating boolean CSPs): If $\Im_{0}$ is a max-$\mathscr{P}$ instance on $m$ variables with $\max(\Im_{0})\leqslant s$ and $\overline{\textup{sos}}_{d}(\Im_{0})>c$, then $f=c-\Im_{0}$ has sos degree larger than $d$. Our main theorem gives a lower bound on the psd rank of the matrix $M^{f}_{n}$. Since this matrix is a submatrix of the matrix in Proposition 1.13, our psd rank lower bound implies a lower bound on the minimum dimension of a subspace achieving a $(c,s)$-approximation for \textup{{max-\mathscr{P}}}_{n}.

Since $U$ achieves a $(c,s)$-approximation for $\Pi_{n}$, for every instance $\Im\in\Pi_{n}^{\leqslant s}$ we will have $\overline{\textup{sos}}_{U}(\Im)\leqslant c$. By definition of $\overline{\textup{sos}}_{U}(\Im)$, this implies that $c-\Im=\sum_{i}g_{i}^{2}$ for $g_{i}\in U$. By expressing each $g_{i}^{2}$ as $g_{i}^{2}=\operatorname{Tr}(\Lambda_{i}Q(x))$ for some $\Lambda_{i}\in\mathcal{S}_{r}^{+}$ we get,

Proof overview and setup

If $H$ comes equipped with a canonical (ordered) orthonormal basis (as will always be the case throughout), we represent linear operators on $H$ by matrices with rows and columns indexed by the basis elements. In this case, $\mathcal{M}(H)$ consists of symmetric matrices and $\mathcal{D}(H)$ consists of symmetric, positive semidefinite matrices whose diagonal entries summing to one. If $A\in\mathcal{M}(H)$ is positive semidefinite, we use $A^{1/2}$ to denote the positive semidefinite square root of $A$.

Given a linear operator $A:H\to H$, we define the operator, trace, and Frobenius norms, respectively:

Recall $\operatorname{Tr}(A^{T}B)\leqslant\|A\|\cdot\|B\|_{*}$ and the Cauchy-Schwarz inequality $\operatorname{Tr}(A^{T}B)\leqslant\|A\|_{F}\|B\|_{F}$. For a matrix $M$, we use $\|M\|_{\infty}$ to denote the maximum absolute value of an entry in $M$.

2 Factorizations, quantum learning, and pseudo-densities

This contradicts $\deg_{\mathsf{sos}}(f)=d+2$ since $\|\sqrt{P(S)}R(x)\|_{F}^{2}$ is a sum of squares of a polynomials of degree less than $d/2$.

By appealing to convex duality, it is possible to construct a certificate that the matrix $M_{n}^{f}$ does not admit low degree factorizations. The certificate consists of a linear functional that separates $M_{n}^{f}$ from the convex hull of matrices that admit low degree psd factorizations. Formally, if we define the convex set $\mathcal{C}_{d}$ of non-negative matrices as,

then we will construct a linear functional $L$ on $\binom{n}{m}\times 2^{n}$ matrices such that

The linear functional is precisely the one derived from what we refer to as a pseudo-density.

Consider a matrix $N\in\mathcal{C}_{d}$ which admits a low degree psd factorization given by $N(S,x)=\operatorname{Tr}(P(S)R(x)^{2})$. Then since $D$ is a degree-$d$ pseudo-density, we would have

However, since $D$ is negatively correlated with $f$,

Formally, for a number $r\geqslant 1$, consider the following set $\mathcal{C}_{r}$ of nonnegative matrices,

Fix a matrix $N\in\mathcal{C}_{r}$. It is instructive to have the situation $\lVert N\rVert_{1},\lVert N\rVert_{\infty}=\Theta(1)$ in mind for the rest of this outline. By definition of $\mathcal{C}_{r}$, the matrix $N$ admits a psd factorization of rank $O(r)$. In light of the above discussion, our goal is to approximate the matrix $N$ by a low degree factorization with respect to the functional $L_{D}$. A low degree approximation for $N$ is constructed in two steps.

Well-behaved factorizations. The first step involves obtaining a nicer factorization of $N$. Toward this end, we define the quantity

Applying the above lemma to the matrix $N$ at hand, we get a psd factorization $N(S,x)=\operatorname{Tr}(P(S)Q(x))$ wherein $\lVert P(S)\rVert$ and $\lVert Q(x)\rVert_{*}$ are bounded polynomially in $r$. This analytic control on the factorization will be important for controlling error bounds, but also—in a more subtle way—for the next step.

Now, if $\mathcal{T}$ is a family of test functionals, then a canonical way of finding a “simple” approximation to $U_{Q}$ that satisfies all the tests is via the following maximum-entropy (convex) optimization problem:

where we recall that $S(\cdot)$ denotes the quantum entropy functional. Moreover, one can attempt to solve this optimization by some form of projected sub-gradient descent. Interpretations of this algorithm go by many names, notably the “matrix multiplicative weights update method” and “mirror descent” with quantum entropy as the regularizer; see, e.g., [NY83, BT03, TRW05, AK07, WK12] and the recent survey [Bub14].

Let $\kappa\geqslant 1$ and $\omega>0$ be given. Define

and for all tests $\Lambda\in\mathcal{T}_{\kappa,\omega}$,

In other words, the learning algorithm produces a hypothesis with error at most $\varepsilon$ for all the tests in $\mathcal{T}_{\kappa,\omega}$; moreover, the hypothesis is the square of a polynomial whose degree is not much larger than that of the tests. The value $\omega$ corresponds to the ubiquitous “width” parameter and, as in most applications of the multiplicative weights method, bounding $\omega$ will be centrally important. The reader should also take note of the appearance of the relative entropy in the degree bound (2.8). It will turn out that low psd rank factorizations will give us functions $Q:\{0,1\}^{n}\to\mathcal{S}_{+}^{k}$ with high entropy (and thus small relative entropy with respect to the uniform state); this is actually a direct consequence of the factorization rescaling in Lemma 2.1.

Then from the definition of $M_{n}^{f}$, we have

On the other hand, we will prove the following theorem in Section 3.1.

Now if we consider the normalized matrix $N=M^{f}_{n}/\lVert M^{f}_{n}\rVert_{\infty}$, we see that it satisfies the first premise $\lVert N\rVert_{\infty}\leqslant 1$ but violates the conclusion of the theorem (because of (2.9)). Therefore we know that the second premise is violated, which gives the lower bound

Since this achieves our goal, we are left to explain why Theorem 2.3 should be true, at least when we apply it with $N=M_{n}^{f}/\|M_{n}^{f}\|_{\infty}$. If we apply $L_{D}$ to the right-hand side of (2.1)—our presumed factorization for $M^{f}_{n}$—we arrive at the expression

We can view this as a test on $Q$ in the sense of Theorem 2.2. Since $\deg(D)\leqslant m$ (because $D$ is only a function of $m$ variables), this is a low-degree test. Theorem 2.2 then suggests that we can replace $Q$ by a low-degree approximator $R^{2}$, while losing only $\varepsilon$ in the “accuracy” of the test.

Since the approximation property implies that $Q(x)$ and $R(x)^{2}$ should perform similarly under the test (up to the “accuracy” $\varepsilon$), we would conclude that $L_{D}(M_{n}^{f})\geqslant-\varepsilon$, yielding the conclusion of Theorem 2.3.

Random restriction and degree reduction. The one serious issue with the preceding argument is that our supposition is far too strong: One cannot expect to have $\deg(R)\leqslant d/2$. Indeed, the guarantee of Theorem 2.2 tells us that the approximator $R(x)$ has degree at most $K\cdot\deg(D)$ for some (possibly large) number $K$ (which itself depends on many parameters). To overcome this problem, we use another crucial property of our functional (2.4): It is an expectation over small sets $S\subseteq[n]$. If we randomly choose such a subset with $|S|=m\ll n$ and randomly choose values $y_{\bar{S}}$ for the variables in $\bar{S}$, we expect that the resulting (partially evaluated) polynomial $R(x_{S},x_{\bar{S}})|_{x_{\bar{S}}=y_{\bar{S}}}$ will satisfy $\deg(R(x_{S},x_{\bar{S}})|_{x_{\bar{S}}=y_{\bar{S}}})\ll\deg(R)$. (Strictly speaking, this will only be true in an approximate sense.)

It is precisely this degree reduction property of random restriction that saves the preceding sketch. In the next sections, we perform a more delicate quantitative analysis capable of achieving much stronger lower bounds. The norm $\|D\|_{\infty}$ of the pseudo-density will play a central role in this study. Thus in Section 5.1, we show that Grigoriev’s proof of Theorem 1.12 can be carefully recast in the language of pseudo-densities such that the resulting pseudo-density has small norm.

PSD rank and sum-of-squares degree

We now move to proving the main technical theorems of the paper along the lines of the informal overview presented in Section 2.2.

we have $L_{D}(N)\geqslant-\varepsilon$. Moreover, this holds for

The proof of this theorem consists of two parts. First, we observe that if $D$ is a degree-$d$ pseudo-density, then $L_{D}(N)$ is nonnegative for all matrices $N$ that admit a factorization in terms of squares of low-degree polynomials, i.e., a factorization $N(S,x)=\operatorname{Tr}(A_{S}^{2}B_{x}^{2})$ for symmetric matrics $\{A_{S}\}$ and $\{B_{x}\}$ such that the function $x\mapsto B_{x}$ has degree at most $d/2$ over $\{0,1\}^{n}$.For the convenience of the reader, we recall that the degree of the matrix-valued function $x\mapsto B_{x}$ is defined as the maximum degree of the functions $x\mapsto(B_{x})_{ij}$ where $i,j$ range over the indices of $B_{x}$. Indeed, consider such a factorization. Then,

As explained in Section 2.2, this guarantee is not sufficient for us. The following theorem (proved in Section 3.2) allows us to analyze $L_{D}$ even when the degree of the map $x\mapsto B_{x}$ is much larger than $d/2$. (For $m\leqslant n^{o(1)}$, it will be the case that the linear functional $L_{D}$ is approximately nonnegative on $N$ even when $x\mapsto B_{x}$ has degree up to $n^{o(1)}$).

$M_{i,j}\leqslant\operatorname{Tr}(P_{i}Q_{j})\leqslant M_{i,j}+\eta\|M\|_{\infty}$,

Note that Item 2 holds by construction. Also observe that

verifying Item 1. Finally, we have the inequalities for all $i\in[p],j\in[q]$,

The first inequality verifies Item 3 since $r\geqslant 1$ and $\eta\leqslant 1$. The last inequality implies that

satisfying the conclusions of the theorem.

where the last inequality has used $\|N\|_{\infty}\leqslant 1$.

From Theorem 3.3(4), the density matrix $Q$ satisfies

Theorem 3.3(1) allows us to lower bound $L_{D}(N)$ in terms of the matrix $(S,x)\mapsto\operatorname{Tr}(P_{S}Q_{x})$ and value $\|D\|_{\infty}$:

Theorem 3.3(2) allows us to upper bound the spectral norm of $F$ by

The next theorem allows us to lower bound $\operatorname{Tr}(FQ)$ by replacing $Q$ with a simpler density matrix that is a low-degree polynomial in $F$. (See Theorem 4.1, where a slightly more general version is proved.)

Apply Theorem 3.4 to the density matrix $Q$ and the symmetric matrix $F$ defined above with the value $\varepsilon$ (which is already fixed). Let $p$ be the resulting degree-$k$ polynomial, with $k$ satisfying the bounds of the theorem.

We have now assembled all components of the proof of Theorem 3.1.

We lower bound the linear functional $L_{D}(N)$ by

Now set $\eta\mathrel{\mathop{:}}=\min(\varepsilon/\|D\|_{\infty},1)$ and use (3.1) to bound $\tau\leqslant 1+\eta\leqslant 2$. This yields

Now recall that our invocation of Theorem 3.4 gives us a bound on $k=\deg(p)$:

Plugging this bound into (3.8) yields, for some constant $c^{\prime}>0$,

2 Degree reduction

The next theorem is a restatement of Theorem 3.2. One should simply note that for any symmetric matrix $A$, we have $\|A\|_{F}^{2}=\operatorname{Tr}(A^{2})$.

For the sake of this lemma, which uses Fourier analysis, we will think of $B$ and $D$ as functions on $\{-1,1\}^{n}$. Since this is a linear transformation on the domain, it does not affect their degrees as multilinear polynomials.

For every $S\subseteq[n]$ with $\lvert S\rvert=m$, we decompose $B$ into two parts $B=B_{S,\mathsf{low}}+B_{S,\mathsf{high}}$ such that $B_{S,\mathsf{low}}$ is the part of $B$ with degree at most $d/2$ in the variables $S$:

(Recall Section 2.1 for the Fourier-analytic definitions.)

The proof consists of two steps that are captured by the following two lemmas.

Let $\tau=\max_{S}\lVert A(S)^{2}\rVert$. Then,

Here, we have used that the quadratic formula $\lVert AB\rVert_{F}^{2}=\lVert AB_{\mathsf{low}}\rVert_{F}^{2}+\lVert AB_{\mathsf{high}}\rVert_{F}^{2}+2\langle AB_{\mathsf{low}},AB_{\mathsf{high}}\rangle$, where $\langle\cdot,\cdot\rangle$ is the inner product that induces $\lVert\cdot\rVert_{F}$, i.e., $\langle X,Y\rangle=\operatorname{Tr}(X^{T}Y)$. Hence,

The first step used the identity $\lvert x^{2}-y^{2}\rvert=\lvert x+y\rvert\cdot\lvert x-y\rvert$. In the second step, we applied Cauchy–Schwarz. The third step used the triangle inequality, $\left\lvert\vphantom{\bigoplus}\lVert AB\rVert_{F}-\lVert AB_{\mathsf{low}}\rVert_{F}\right\rvert\leqslant\lVert AB_{\mathsf{high}}\rVert_{F}\,.$

This bound implies the desired lower bound

By construction the Fourier transform of $B_{S,\mathsf{high}}$ satisfies

We combine the previous two lemmas to lower bound the correlation between the pseudo-density $D(x_{S})$ and the norms $\lVert A(S)B(x)\rVert_{F}^{2}$,

3 Proof of the main theorem

For a function $f\colon\{0,1\}^{m}\to$ and an integer $n\geqslant m$, let $M^{f}_{n}\colon\binom{n}{m}\times\{0,1\}^{n}\to$ be the matrix,

For any $m,d\geqslant 1$, the following holds. Let $f:\{0,1\}^{m}\to$ be a nonnegative function with $d+2=\deg_{\mathsf{sos}}(f)$. Then for $n\geqslant 2m$,

where $C_{f}>0$ is a constant depending only on $f$.

which yields an explicit psd factorization of $M^{f}_{n}$ with matrices $\{P_{S}\},\{Q_{x}\}$ of dimension $r=\sum_{i\leqslant 1+d/2}\binom{n}{i}\leqslant 1+n^{1+d/2}$. ∎

Approximations for density operators

We turn now to a central theme of our approach: High-entropy states can be approximated by “simple” states if the approximation is only with respect to “simple” tests. In our setting, “simple” will mean low-degree. In Section 4.1, we present a basic version of this principle with respect to a single test functional. This suffices for essentially all our applications to psd rank lower bounds.

We believe that the maximum-entropy approximation framework is a powerful one, so Section 4.2 is devoted to a more general exploration of the principle. In particular, we state and prove approximation theorems for density operators with respect to families of tests. In the rest of this section, we fix a finite-dimensional real inner product space $H$.

Let $F\in\mathcal{M}(H)$ be a symmetric matrix and let $Q\in\mathcal{D}(H)$ be a density matrix. Then, for every $\varepsilon\in(0,\frac{1}{2})$, there exists a degree-$k$ univariate polynomial $p$ with $k\leqslant O(\lVert F\rVert/\varepsilon)\cdot S(Q\,\|\,U)+O\left(\frac{\log 1/\varepsilon}{\log\log 1/\varepsilon}\right)$ such that

Moreover, the polynomial $p$ depends only on $\varepsilon$, the operator norm $\lVert F\rVert$, and the relative entropy $S(Q\,\|\,U)$.)

The proof consists of two steps. First, we will show that the theorem holds with $\tfrac{1}{\operatorname{Tr}(p(F)^{2})}p(F)^{2}$ replaced by $e^{-\lambda F}/\operatorname{Tr}(e^{-\lambda F})$ for $\lambda\leqslant(1/\varepsilon)\cdot S(Q\,\|\,U)$. Then, we will approximate the matrix exponential by the square of a low-degree polynomial.

For every symmetric matrix $F$ and every density matrix $Q$,

as long as $\lambda\geqslant 1/\varepsilon\cdot S(Q\,\|\,U)$.

By the duality formula for quantum entropy (see, e.g., [Car10, Thm. 2.13]), the function $f:X\mapsto\lambda\operatorname{Tr}(FX)+S(X\,\|\,\mathcal{U})$ over the the set of density matrices is minimized at $X^{\star}=e^{-\lambda F}/\operatorname{Tr}(e^{-\lambda F})$. Therefore, using the fact $S(X^{\star}\,\|\,\mathcal{U})\geqslant 0$, we get

which implies that $\operatorname{Tr}(FX^{\star})\leqslant\operatorname{Tr}(FQ)+S(Q\,\|\,\mathcal{U})/\lambda\leqslant\operatorname{Tr}(FQ)+\varepsilon$, as desired. ∎

Next we observe that one can pass from univariate approximations of $e^{x}$ to approximations of $e^{F}$ in the trace norm.

Let $\delta\in(0,1]$ and $\tau>0$ be given. Suppose there exists a univariate polynomial $p(x)$ such that for every $x\in[-\tau/2,\tau/2]$,

Then for every $F\in\mathcal{M}(H)$ with $\|F\|\leqslant\tau$, we have

Under the assumptions, for every $x\in[-\tau,\tau]$, one has

where the last line follows from $\delta\leqslant 1$. Note the elementary equality: For all $x,y,x^{\prime},y^{\prime}>0$,

Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\in[-\tau,\tau]$ denote the eigenvalues of $F$. We conclude that

Since $e^{F}$ and $p(F)$ are simultaneously diagonalizable, the preceding inequality is precisely our goal (4.2). ∎

The following corollary of Lemma 4.3 follows by checking that the Taylor expansion of $e^{x}$ satisfies the approximation guarantee (4.1).

For every $\varepsilon\in(0,\frac{1}{2})$ and every symmetric matrix $F\in\mathcal{M}(H)$, there is a number $k\leqslant 3e\left(\|F\|_{\infty}+\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}\right)$ and a univariate degree-$k$ polynomial $p_{k}$ with non-negative coefficients such that

Let $p_{k}(x)=\sum_{t=0}^{k}\frac{x^{k}}{k!}$. By Taylor’s theorem, we have

Define $\tau=\|F\|_{\infty}$ and choose $k=\left\lfloor 3e\left(\tau+\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}\right)\right\rfloor$ so that for $x\in[-\tau/2,\tau/2]$, we have $\frac{x^{k+1}}{(k+1)!}\leqslant\varepsilon/6$. Finally, apply Lemma 4.3. ∎

The proof of the main theorem in this section follows by combining Lemma 4.2 and Corollary 4.4.

Fix $\varepsilon\in(0,\frac{1}{2})$ and $F\in\mathcal{M}(H)$, $q\in\mathcal{D}(H)$. Choose $\lambda=(2/\varepsilon)\cdot S(Q\,\|\,\mathcal{U})$ and $F^{\prime}=-\lambda F$. Let $p_{k}$ be the polynomial from Corollary 4.4 for $k=3e\left(\lVert F^{\prime}\rVert+\frac{\log(1/\varepsilon^{\prime})}{\log\log(1/\varepsilon^{\prime})}\right)$ and $\varepsilon^{\prime}=\varepsilon/(2\lVert F\rVert)$. Note that $k\leqslant O(\lVert F\rVert/\varepsilon)\cdot S(Q\,\|\,\mathcal{U})+O\left(\frac{\log 1/\varepsilon}{\log\log 1/\varepsilon}\right)$. Moreover,

Since $\varepsilon/2+\varepsilon^{\prime}\cdot\lVert F\rVert\leqslant\varepsilon$, the polynomial $p(x)=p_{k}(-\lambda x/2)$ satisfies the desired bound

2 Approximation against a family of tests

Let $\mathcal{T}\subseteq\mathcal{M}(H)$ denote a compact set of matrices, and set $\Delta(\mathcal{T})\mathrel{\mathop{:}}=\sup_{A\in\mathcal{T}}\|A\|$. For $A\in\mathcal{M}(H)$, we define the associated dual gauge

One should think of $\mathcal{T}$ as a set of test functionals; for $A,A^{\prime}\in\mathcal{M}(H)$, the value $[A-A^{\prime}]_{\mathcal{T}}$ measures the extent to which $A$ and $A^{\prime}$ are distinguishable using tests from $\mathcal{T}$. It is important to note that if $\mathcal{T}$ is not centrally symmetric, then $[\cdot]_{\mathcal{T}}$ might also fail to be symmetric. For future reference, we observe that fact that for any $A\in\mathcal{M}(H)$,

Our main approximation theorem asserts that, with respect to tests from a convex set $\mathcal{T}$, a high-entropy density operator can be well-approximated by the square of a low-degree polynomial in some element of $\mathcal{T}$.

For every $\varepsilon\in(0,\frac{1}{2})$, the following holds. Let $\mathcal{T}\subseteq\mathcal{M}(H)$ be compact and convex, and let $Q\in\mathcal{D}(H)$ be a density matrix. Then there exists a number

a univariate degree-$k$ polynomial $p$, and an element $F\in\mathcal{T}$ such that $\operatorname{Tr}(p(F)^{2})=1$ and

This can be verified immediately by showing that both sides satisfy the differential equation

with $F(0,t)=0$ for all $t$. (This argument is taken from [Wil67].)

We will only require (4.8) for $\beta=1$. For example, (4.8) and cyclicity of the trace yields

Denote $X^{\prime}(t)=\frac{dX(t)}{dt}$. If we know that $X(t)$ is symmetric, and its eigenvalues are $\{\lambda_{i}\}$, then by diagonalizing in the basis of $X(t)$, we can also derive

where in the final line we have used the fact that if $a\geqslant b$, then

since $e^{b-a}\geqslant 1+(b-a)$. Thus we have

We will use this for the following lemma.

For every $\varepsilon>0$, the following holds. Let $\mathcal{C}\subseteq\mathcal{M}(H)$ be a compact set, and let $Q,Q_{0}\in\mathcal{D}(H)$ be density matrices. If one defines $h=\lceil\frac{8}{\varepsilon^{2}}S(Q\,\|\,Q_{0})\Delta(\mathcal{T})^{2}\rceil$ then there exist $A_{1},A_{2},\ldots,A_{h}\in\mathcal{T}$ such that

Consider for $t\geqslant 0$, the density matrix

where $s\mapsto\Lambda_{s}\in\mathcal{T}$ is any measurable function.

where in the final line we have used $\operatorname{Tr}(Q)=1$.

Let $T=\frac{2}{\varepsilon}S(Q\,\|\,Q_{0})$. Suppose the map $t\mapsto\Lambda_{t}\in\mathcal{T}$ is such that

Then from (4.15) and (4.16), we arrive at

which contradicts the fact that $S(Q\,\|\,Q_{T})\geqslant 0$.

and define $\Lambda_{t}=A_{i+1}$ for $t\in(t_{i},t_{i+1}]$.

Finally, observe that for $t\in(t_{i},t_{i+1})$, we have

where we have used the fact that $\Lambda_{t}=-\frac{d}{dt}\log\left(e^{\log Q_{0}-\int_{0}^{t}\Lambda_{s}\,ds}\right)$. We conclude that

with $|\lambda|\lesssim 1+\frac{1}{\delta}S(Q\,\|\,U)$ and which satisfies

Note here that since $\mathcal{T}$ is assumed to be convex, we have $F\in\mathcal{T}$ (see the form of (4.12)).

Then we apply Corollary 4.4 to $\lambda F$ to obtain a degree-$k$ polynomial $p_{k}$ such that

for the relative entropy between $f\mu$ and $\mu$. We will also allow ourselves to conflate $\mu$ with the corresponding density by writing $\mu(x)$ for $\mu(\{x\})$ and $x\in X$. One should note that an analog of Lemma 4.6 for the special case of probability distributions (instead of density matrices) can be proved exactly along the same lines, but without the use of matrix inequalities.

We also lift each test $g$ to a matrix $M(g)=\sum_{x\in\{0,1\}^{n}}g(x)e_{x}e_{x}^{T}$ and the set $M(\mathcal{T})$ now denotes a class of matrix tests.

so that $S(M(f)\,\|\,Q_{0})=D(f\,\|\,\mu)$.

and such that for every $g\in\mathcal{T}$,

The correlation polytope

This polytope is also known as the Boolean quadric polytope [Pad89] for the following reason.

where $A$ is the matrix $A=(a_{ij})$. Since this inequality holds at the vertices, it holds for all of $\text{{{corr}}}_{n}$. ∎

We now recall the relationship between the correlation, cut, TSP, and stable set polytopes. The first fact is from [DS90], while the second two are taken from [FMP+12].

For every $n\geqslant 1$, the following hold:

$\text{{{corr}}}_{n}$ is linearly isomorphic to $\text{{{cut}}}_{n+1}$.

There exists a number $a_{n}\leqslant O(n^{2})$ such that some face of $\text{{{tsp}}}_{a_{n}}$ linearly projects to $\text{{{corr}}}_{n}$.

There exists a graph $H_{n}$ on $b_{n}\leqslant O(n^{2})$ vertices such that some face of $\text{{{stab}}}_{b_{n}}(H_{n})$ linearly projects to $\text{{{corr}}}_{n}$.

We will now prove a lower bound on the psd rank of $\text{{{corr}}}_{n}$. Our first goal is to construct a suitable family of pseudo-densities. We will employ Grigoriev’s work [Gri01a] on degree lower bounds for Positivstellensatz calculus refutations. The primary difficulty will be in expressing Grigoriev’s lower bound using a pseudo-density of small norm.

Grigoriev constructs a linear functional $\mathcal{G}$ on the space of $m$-variate real polynomials modulo the ideal $\mathcal{I}$ generated by $\{X_{i}^{2}-X_{i}:i=1\in[m]\}$:

The functional is uniquely defined by the values

for each multilinear monomial $X^{S}=\prod_{i\in S}X_{i}$ with $S\subseteq[m]$. Observe that $m/2$ is not an integer and the (generalized) binomial coefficient $\binom{m/2}{k}$ is defined using the formal expression

It is easy to check that $\mathcal{G}$ satisfies (5.2):

Grigoriev shows that $\mathcal{G}$ satisfies (5.1) [Gri01a, Lem. 1.4].

We claim that for any univariate real polynomial $p$ with $\deg(p)\leqslant m$,

Both sides of the claimed identity are univariate polynomials in $t$ of degree at most $m$ and agree with each other on the $m+1$ points given by $t\in\{0,1,\ldots,m\}$. Hence, the two polynomials are identically equal.

For each $x\in\{0,1\}^{m}$, let $|x|$ denote its hamming weight, and define

Finally, in order to bound $\lVert D\rVert_{\infty}$, observe that the polynomials $c_{w}(t)$ are given by the interpolation formula

For an $x\in\{0,1\}^{m}$ with $|x|=w$ we have,

where in the last step we have used Sterling’s approximation for the inequality $\binom{m-1}{(m-1)/2}\leqslant 2^{m-1}/\sqrt{\frac{3}{2}(m-1)+1}$, valid for $m\geqslant 3$. ∎

There is a constant $\alpha>0$ such that for every $n\geqslant 1$,

Choosing $n\geqslant\frac{2}{\alpha^{\prime}}m^{13/2}\log n$, an easy calculation shows that

Optimality of low-degree sum-of-squares for max CSPs

Constraint satisfaction problems form a broad class of discrete optimization problems that include, for example, max cut and max 3-sat. For simplicity of presentation, we will focus on constraint satisfaction problems with a boolean alphabet, though similar ideas extend to larger domains (see an analogous generalization in Section 7). We begin our presentation with a formal definition of semidefinite programming relaxations for max-CSPs.

Given an instance \Im\in\textup{{max-\Pi}}_{n}, the SDP relaxation $\mathcal{S}$ has value

The degree-$d$ sos relaxation for $\Im$ is given by

We will now write the dual formulation of the above semidefinite program to expose the underlying spectrahedron and linearization. The dual of (6.1) can be written as,

where the final inequality used the fact that $\langle D,g^{2}\rangle\geqslant 0$ for all functions $g$ with $\deg(g)\leqslant d/2$.

From the above discussion, it is clear that the feasible region of the degree $d$-sos relaxation (6.2) corresponds to the spectrahedron,

From (6.3) and (6.4), for every instance \Im\in\textup{{max-\Pi}}_{n} and every assignment $x\in\{0,1\}^{n}$ we have

Now the degree-$d$ sos relaxation corresponding to an instance \Im\in\textup{{max-\Pi}}_{n} in (6.1) and (6.2) can be equivalently formulated as

where the first index of $M^{n,\Pi}_{c,s}$ ranges over all instances on $n$ variables satisfying $\operatorname{opt}(\Im)\leqslant s$. A simple consequence of Proposition 1.10 is the following.

2 General SDPs vs. sum-of-squares

Our main theorem is that general SDP relaxations for max-CSPs are no more powerful than low-degree sum-of-squares relaxations in the polynomial-size regime.

Given that the degree-$d$ sos relaxation cannot achieve a $(c,s)$-approximation, there exists an instance $\Im$ of \textup{{max-\Pi}}_{m} for some $m$ such that $\operatorname{opt}(\Im)\leqslant s$ but $\deg_{\mathsf{sos}}(c-\Im)>d$.

This implies that no sequence of SDP relaxations of size at most $o((\frac{n}{\log n})^{d/4})$ can achieve a $(c,s)$-approximation for max-$\Pi$. ∎

For a stronger quantitative bound, we require the following simple fact.

Write $\chi_{\alpha}=\chi_{A}\chi_{B}$ for some $A,B$ with $|A|,|B|\leqslant d/2$ and observe that

Suppose that for every $n\geqslant 1$, the degree-$d(n)$ sos relaxation cannot achieve a $(c+\varepsilon,s)$-approximation for \textup{{max-\Pi}}_{n}. Then for all $n\geqslant 1$, no SDP relaxation of size at most $Kn^{d(n)^{2}/8}$ can achieve a $(c,s)$-approximation for \textup{{max-\Pi}}_{N} for every $N>n^{4d(n)}$.

Using known lower bounds for low degree sum-of-squares relaxations for max-CSPs [Gri01b, Sch08, Tul09], Theorem 6.4 implies lower bounds against general SDP relaxations for a range of specific max-CSPs. For instance, the lower bounds of Grigoriev [Gri01b] and Schoenebeck [Sch08] imply a lower bound for max 3-sat (see Theorem 1.5).

For every $\varepsilon>0$, there exists a constant $c_{\varepsilon}$ such that the following holds. For every $n\geqslant 1$, there is a \textup{{max-\Pi}}_{n} instance $\Im_{n}$ such that $\operatorname{opt}(\Im_{n})\leqslant 7/8+\varepsilon$, but $\overline{\textup{sos}}_{c_{\varepsilon}n}(\Im)=1$.

Observe that one can obtain the bound of Theorem 1.5 using the preceding result as follows. In Theorem 6.4, choose $n\asymp\log N$ and $d(n)\asymp\frac{\log N}{\log\log N}$ so that $n^{4d(n)}\asymp N$. In that case, the lower bound obtained is of the order $N^{d(n)/32}\asymp N^{\Omega(\log N/\log\log N)}$.

Nonnegative rank

Theorem 3.8 exhibits a connection between psd rank and sos degree. There is a similar connection between nonnegative rank and junta-degree. The results of Section 7.1 generalize those of [CLRS13], while the method of proof is closely related. As opposed to [CLRS13], we use the learning approach of Section 4 to approximate by juntas. In Section 7.2, we demonstrate an application to the correlation polytope.

We also define a more quantitative notion: Approximate junta degree with respect to an arbitrary measure. Given $\varepsilon>0$ and a measure $\mu$ on $X^{n}$, we define

where we take the maximum to be equal to $-1$ if no such pseudo-density exists. (See Section 7.2 for an example where a biased measure $\mu$ is used to analyze the nonnegative rank of the lopsided disjointness matrix.) We can now state our main theorem on nonnegative rank.

where $d+1=\deg_{\mathsf{J}}^{\varepsilon}(f;\mu^{m})$ and $c>0$ is a universal constant.

The left-hand-side inequality of (7.1) follows from the fact that the cone of nonnegative $d$-juntas is spanned by $\sum_{i=0}^{d+1}\binom{n}{i}\leqslant 1+n^{d+1}$ nonnegative $d$-juntas. We move on to right-hand inequality.

Let $\Lambda_{\tau}=\{i:\|q_{i}\|_{\infty}\leqslant\tau\}$. Note that for $i\notin\Lambda_{\tau}$, we must have

Let $J_{i}$ denote the set of coordinates on which $q_{i}$ depends, so that $|J_{i}|\leqslant k^{\prime}$.

We break the right-hand side of (7.2) into two parts. First, using (7.4),

For the second part, we use (7.5) so that for every $i\in\Lambda_{\tau}$ and $|S|=m$,

This implies that for $i\in\Lambda_{\tau}$,

where in the final line we have used $\|\lambda_{i}\|_{\infty}\leqslant\|f\|_{1}$ from (7.3) and also $|J_{i}|\leqslant k^{\prime}$ and $n\geqslant 2m$.

Combining this with (7.7) and (7.6), we conclude that

Let us now set $\tau=3r\frac{\|f\|_{\infty}}{\|f\|_{1}}$ and $\delta=\varepsilon\|D\|_{\infty}/3$, yielding

Now, if $r\geqslant n^{d}$, then we are done. Otherwise, (7.8) yields

2 The correlation polytope and lopsided disjointness

We now illustrate a particularly simple application of our method to nonnegative rank.

and let $\mu$ be the measure on $\{0,1\}$ satisfying $\mu(0)=1-2/m$ and $\mu(1)=2/m$. Then,

Plugging this result into Theorem 7.2 yields the following.

There is a constant $c>0$ such that for every $m\geqslant 3$ and $n\geqslant 2m$, we have

We now verify that $D$ is a $d$-local pseudo-density (with respect to $\mu^{m}$) for $d=\frac{m}{2}+1$. Observe first that

Let $\beta=\frac{2}{m}\left(1-\frac{2}{m}\right)^{m-1}$ denote $\mu^{m}(1,0,\ldots,0)$. Consider a subset $S\subseteq[m]$ and some fixed string $b\in\{0,1\}^{S}$. Let $\bm{1}_{b}:\{0,1\}^{m}\to\{0,1\}$ denote the indicator of whether $x_{S}=b$. If $b=\mathbf{0}$, then

The latter quantity is nonnegative as long as $|S|\leqslant\frac{m}{2}+1$.

In other words, the lower bound of Theorem 7.4 applies to all matrices that have a subset of entries corresponding to the unique disjointness problem.

3 Unique games hardness for LPs

As an illustrative application of the relation between nonnegative rank and junta-degree (Theorem 7.2), we present an LP hardness result for the Unique Games problem.We thank Ola Svensson for the suggestion to make this explicit.

Fix an integer $q\geqslant 1$. An instance $\Im$ of unique games $\textup{{UG}}^{q}$ consists of variables $X_{1},\ldots,X_{n}$ taking values in $[q]$ and a collection of predicates $P_{1},\ldots,P_{M}$ over these variables. Each constraint $P_{i}$ is over a pair of distinct variables $\{X_{a_{i}},X_{b_{i}}\}$ and is specified by a bijection $\pi_{i}:[q]\to[q]$ as follows:

The goal is to find an assignment that maximizes, over $x\in[q]^{n}$, the number of satisfied constraints:

Recall that $\operatorname{opt}(\Im)=\max_{x\in[q]^{n}}\Im(x)$. Let $\textup{{UG}}^{q}_{n}$ denote the family of Unique Games instances on $n$ variables. The authors of [CMM09] exhibit a strong integrality gap for Sherali-Adams linear programming relaxations of $\textup{{UG}}^{q}$

Fix a number $t\geqslant 1$ and let $q=2^{t}$. Then for every $\delta>0$, there exist $\gamma,\varepsilon>0$, an $m\geqslant 1$, and an instance $\Im\in\textup{{UG}}^{q}_{m}$ such that

but $\deg_{\mathsf{J}}^{\varepsilon}(1-\delta-\Im)\geqslant m^{\gamma}$.

In fact, the authors of [CMM09] construct a lower bound for the $d$-round Sherali-Adams LP relaxation (where $d\asymp m^{\gamma})$. But there is an equivalence between such lower bounds and the existence of a $d$-local pseudo-density; we refer to [CLRS13] for a discussion. Applying Theorem 7.2 (with $X=[q]$ and $\mu$ as the uniform measure on $[q]$), we obtain the following corollary.

Let $M^{n,\textup{{UG}}^{q}}_{c,s}$ denote the matrix with entries

where $\Im$ runs over all $\textup{{UG}}^{q}_{n}$ instances with $\operatorname{opt}(\Im)\leqslant s$, and all values $x\in[q]^{n}$.

For every $t\geqslant 1$, $\delta>0$, and $d\geqslant 1$, there exists a constant $c>0$ such that for all $n\geqslant 1$,

In the language of [CLRS13] (see also Section 6 for related definitions in the SDP setting), this shows that polynomial-size families of LP relaxations cannot achieve a $(1-\delta,\frac{1}{q}+\delta)$-approximation for the Unique Games problem.

Acknowledgments

This work was supported, in large part, by NSF grant CCF-1407779. A significant fraction of the project was completed during a long-term visit of the authors to the Simons Institute for the Theory of Computing (Berkeley) for the program on Algorithmic Spectral Graph Theory. The authors would also like to thank Paul Beame, Siu-On Chan, Daniel Dadush, Troy Lee, Sebastian Pokutta, Pablo Parrilo, Mohit Singh, Ola Svensson, Thomas Rothvoß, and Rekha Thomas for valuable discussions and comments.

References