The UGC hardness threshold of the L_{p} Grothendieck problem

Guy Kindler^{∗}  Assaf Naor^{†}  Gideon Schechtman^{‡}

Abstract

For p ≥ 2 we consider the problem of, given an n × n matrix A = (a_{ij}) whose diagonal entries vanish, approximating in polynomial time the number

Opt_{p}(A) max {∑_{i,j=1}^{n} a_{ij}x_{i}x_{j} : (x_{1}, …, x_{n}) ∈ ^{n} ∧ (∑_{i=1}^{n} |x_{i}|^{p})^{1/p} ≤ 1} .

When p = 2 this is simply the problem of computing the maximum eigenvalue of A, while for p = ∞ (actually it suffices to take p ≈ logn) it is the Grothendieck problem on the complete graph, which was shown to have a O(logn) approximation algorithm in [27, 26, 15], and was used in [15] to design the best known algorithm for the problem of computing the maximum correlation in Correlation Clustering. Thus the problem of approximating Opt_{p}(A) interpolates between the spectral (p = 2) case and the Correlation Clustering (p = ∞) case. From a physics point of view this problem corresponds to computing the ground states of spin glasses in a hard-wall potential well.

We design a polynomial time algorithm which, given p ≥ 2 and an n × n matrix A = (a_{ij}) with zeros on the diagonal, computes Opt_{p}(A) up to a factor \frac{p}{e} + 30 logp. On the other hand, assuming the unique games conjecture (UGC) we show that it is NP-hard to approximate (2) up to a factor smaller than \frac{p}{e} + \frac{1}{4}. Hence as p → ∞ the UGC-hardness threshold for computing Opt_{p}(A) is exactly \frac{p}{e} (1 + o(1)).

1 Introduction

In this paper we consider the problem of maximizing a multilinear quadratic polynomial over a convex set K ⊆ ^{n}. Namely, given a symmetric n × n matrix A = (a_{ij}) whose diagonal entries vanish, the goal is to approximate in polynomial time the number

max { ∑_{i,j=1}^{n} a_{ij}x_{i}x_{j} : (x_{1}, …, x_{n}) ∈ K}.  (1)

In recent years there has been a lot of work on approximating such polynomials in the special case where K is the hypercube (by convexity, it makes no difference if one considers the solid hypercube [−1, 1]^{n} or the discrete hypercube {−1, 1}^{n}). The case of optimizing over the hypercube has a wide range of applications to combinatorial optimization, and also has connections to topics in classical Banach space theory such as Grothendieck’s inequality. We refer to [27, 26, 4, 15, 3, 5, 23, 2] and the references therein for both positive and negative results in this case, as well as for their applications.

∗Weizmann Institute. Email: gkindler@weizmann.ac.il.

†Courant Institute. Email: naor@cims.nyu.edu. Supported by in part by NSF grants CCF-0635078 and DMS-0528387.

‡Weizmann Institute. Email: gideon@weizmann.ac.il. Supported in part by the Israel Science Foundation.

Optimization over other bodies K is interesting as well. The case where K is a simplex has been investigated in [20, 16], partly in connection to problems in computational biology. The case when K is a polytope with polynomially many facets is classical, and is among the most important non-linear optimization problems, with a wide range of applications in operations research, computational biology and economics (see [17, 10, 13] for more information on the computational complexity of such problems).

In this work our focus is on cases where K is the unit ball in ℓ_{p}^{n} for some parameter p. The specific case mentioned above where K is the hypercube is obtained by setting p = ∞, and it is computationally hard: an O(logn) approximation algorithm is known (it was discovered independently in [29], [28], [25], and [15]), but it was shown to be NP-hard in [31], it was shown NP-hard to approximate within some constant factor in [4], and in [5] it was shown to be NP-hard for any constant factor approximation. The latter paper also showed that getting an approximation factor better than (logn)^{γ} is quasi-NP hard for some universal constant γ > 0, and that even improving on the O(logn) approximation can be ruled out under some plausible complexity assumption.

Setting p = 2, on the other hand, corresponds to the case where K is the Euclidean unit ball, and is much easier computationally. In this case the value in (1) is the maximum eigenvalue of the coefficient matrix A = (a_{ij}), and can be computed efficiently with arbitrarily good precision.

1.1 Our results

It is natural to ask what happens for values of p that lie between 2 and ∞. Roughly speaking, this set of problems can be viewed as a smooth interpolation between Spectral Partitioning and Correlation Clustering (the connection between (1) when K is the hypercube and the Correlation Clustering problem was discovered in [15]). In this paper we investigate these problems and give both new algorithms and complexity lower-bounds (the lower bounds being based on the Unique Games Conjecture). We note that the proofs of our results use the assumption p ≥ 2, and therefore do not apply to the case 1 ≤ p < 2, which we did not investigate. The case p = 1 was studied in [20, 16], and apart from that nothing seems to be known for 1 < p < 2.

The following theorem contains the approximation factors that we can achieve for 2 < p < ∞, as well as the hardness factors that we can prove.

Theorem 1.1. There is a polynomial time algorithm which, given p ≥ 2 and an n×n matrix A = (a_{ij}) whose diagonal entries vanish, computes the number

max { ∑_{i,j=1}^{n} a_{ij}x_{i}x_{j} : (x_{1}, …, x_{n}) ∈ ^{n} ∧ ∑_{j=1}^{n} |x_{j} |^{p} ≤ 1}  (2)

up to a factor \frac{p}{e} + 30 logp.

On the other hand, assuming the unique games conjecture, it is NP-hard to approximate (2) for any constant p > 2 up to a factor smaller than \frac{p}{e} + \frac{1}{4}.

Hence, assuming the unique games conjecture, as p → ∞ the NP-hardness threshold of the quadratic program (2) is \frac{p}{e} (1 + o(1)).

The unique games conjecture (UGC), which has been put forth by Khot [22], is a commonly used assumption in complexity theory. We describe it formally in Section 2. The UGC has been used in the context of hardness results for quadratic programs such as (1) in [23]. In Section 4 we also prove a hardness result for parameters p which depend polylogarithmically on n, based on a strengthening of the UGC. For readers that are not familiar with the UGC let us say at this point that the hardness result in Theorem 1.1 should be viewed as evidence that efficiently computing (2) up to a factor smaller than \frac{p}{e} + \frac{1}{4} is hard.

When p is close to 2. Theorem 1.1 is stated asymptotically as p → ∞, but our hardness result actually shows that for every δ ∈ (0, 1) and p > 2 it is UGC hard to approximate (2) up to a factor smaller than (1 − δ)γ_{p}^{2}, where γ_{p} is the p’th norm of a standard Gaussian random variable. Since

γ_{p} = (\frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}} )^{1/p} ≥ \sqrt{1 + c(p − 2)} ,

where c is universal constant, we also obtain a non-trivial hardness of approximation result for every p > 2.

1.2 The relation to spin glass models.

The problems described above are natural from the point of view of solid state physics, since they are intimately related to the problem of efficient evaluation of ground states of spin glasses. In the spin glass model we are given n particles, denoted by {1, …, n}, each of which has a spin, or magnetization, x_{i} ∈ . The energy corresponding to each pair i, j in the system is proportional to x_{i}x_{j}: we are given an n × n matrix of pairwise interactions A = (a_{ij}) ∈ M_{n}( ) (the diagonal entries are zeros), and the total energy of the system is given by ∑ _{i,j=1}^{n} a_{ij}x_{i}x_{j}. The system is constrained to be in a potential well, or equivalently, there is an external magnetic field acting on the particles. A “hard wall” potential well^{1} would simply correspond to imposing the constraint (x_{1}, …, x_{n}) ∈ K for some K ⊆ ^{n}.

Since nature seems to seek the state where the energy is minimized, many physicists are interested in the computational complexity of computing the ground state, i.e. the configuration which minimizes the total energy of the constrained system. This is precisely the problem described above (with the matrix A replaced by −A). One reason why physicists would be interested in the computation complexity of a ground state is that if this state is hard to find computationally, it may explain (or even predict) why certain systems cannot settle in their ground state. On the other hand, if a system does settle in a computationally-hard ground state, this would imply that it can somehow perform a hard computation.

There is a vast amount of literature on the computational aspects of the evaluation of ground states of physical systems, as this corresponds to understanding efficient mechanisms for pattern formation (see for example [33, 24]). The Ising case of the spin glass model corresponds to the assumption x_{i} = ±1. Computing the ground state in this famous simplified version clearly corresponds to (1) when K is the hypercube. Rigorous algorithmic results on the Ising case were obtained in [12, 9, 7, 3, 8]. The Ising model was introduced as a more tractable simplification of the original spin glass model, and in physically realistic scenarios the magnetization of the particles should be allowed to take real values (actually the most interesting case is when the spins are elements of the 2-dimensional sphere S^{2}).

Our results give strong evidence of a threshold behavior of the computational tractability of the ground state, when the hard wall constraint corresponds to the ℓ_{p}^{n} ball, p > 2. We believe that this phenomenon holds true for more general potentials (see the “Discussion and open problems” section). It would be interesting to find a physical explanation of this computational phase transition^{2}.

1Physicists often also consider “soft constraints”, in which we are given a potential V : ^{n} → and we wish to minimize ∑ _{i,j=1}^{n} a_{ij}x_{i}x_{j} + V(x_{1}, …, x_{n}) (note that this has a similar effect to requiring that (x_{1}, …, x_{n}) is in the set where V(x_{1}, …, x_{n}) is not very large). The case when V(x_{1}, …, x_{n}) = ∑ _{j=1}^{n} v(x_{j}) is called the case of one body potentials, and it is studied explicitly in the physics literature, including the especially important case v(x) = |x|^{p}, which corresponds to the problems studied here (for example, the L_{p} case is studied in [30, 11]).

1.3 About the techniques

The algorithm that we design in Theorem 1.1departs from the standard semidefinite programming approach that was used in [26, 4, 15, 3] by considering the convex program (which is not an SDP for finite p) that computes the quantity

Vec_{p}(A) max { ∑_{i,j=1}^{n} a_{ij}⟨v_{i}, v_{j}⟩ : {v_{1}, …, v_{n}} ⊆ ^{n} ∧ (∑_{i=1}^{n} ∥v_{i}∥_{2}^{p})^{1/p} ≤ 1}.

This program can be solved with arbitrarily small error in polynomial time using Grötschel-Lovász-Schrijver theory [18].

Let v_{1}, …, v_{n} ∈ ^{n} be the the output of this program. In the case p = ∞, which corresponds to the constraint max_{1≤j≤n} ∥v_{j}∥_{2} ≤ 1, one can proceed as follows. Since the value of Vec_{∞} (A) depends only on the scalar products {⟨v_{i}, v_{j}⟩}_{i,j=1}^{n}, we may replace v_{1}, …, v_{n} by Uv_{1}, …, Uv_{n} for any orthogonal matrix U. A standard computation shows that if we choose U uniformly at random among all n × n orthogonal matrices then for each 1 ≤ j ≤ n and t > 0 the probability that (Uv_{j})_{k} (the k^{th} coordinate of Uv_{j}) is greater than \frac{t}{\sqrt{n}} is

at most e^{−Ω(t^{2})} . Hence we can use the union bound to select with positive probability an orthogonal matrix U such that x_{jk} \sqrt{cn/ logn}· (Uv_{j})_{k} ≤ 1 for all 1 ≤ i, j ≤ n, where c is a universal constant. Since by definition

Vec_{∞} (A) = ∑_{i,j=1}^{n} a_{ij}⟨v_{i}, v_{j}⟩ = ∑_{i,j=1}^{n} a_{ij}⟨Uv_{i}, Uv_{j}⟩ = \frac{logn}{c} · \frac{1}{n} ∑_{k=1}^{n} ∑_{i,j=1}^{n} a_{ij}x_{ik}x_{jk},

there exists some 1 ≤ k ≤ n for which ∑ _{i,j=1}^{n} a_{ij}x_{ik}x_{jk} ≥ \frac{c}{logn}Vec_{∞} (A). We therefore get the required O(logn) approximation algorithm (originally obtained in [29, 28, 25, 15]) by rounding v_{j} to x_{jk} ∈ [−1, 1].

For bounded p we wish to obtain a constant factor approximation, so there is no hope to use a union bound. We overcome this problem via a bootstrapping argument which is a non-trivial adaptation of the Gaussian Hilbert space approach to Grothendieck’s inequality [21] (this approach was previously used for algorithmic purposes in [4, 3]). Namely, we take a standard Gaussian vector G ∈ ^{n} and consider the scalars ⟨v_{1}, G⟩, …, ⟨v_{n}, G⟩. Rather than truncating each of the numbers ⟨v_{i}, G⟩ separately, we consider the event E = {∑ _{i=1}^{n} |⟨v_{i}, G⟩|^{p} ≤ M}for some appropriately chosen M > 0. Our rounding algorithm rounds the vector v_{j} to the number x_{j} \frac{1}{M^{1/p}}⟨v_{j}, G⟩1_{E}. We show that this rounding procedure works by bounding the expectation of the error term ∑ _{i,j=1}^{n} a_{ij}⟨v_{i}, v_{j}⟩ − ∑ _{i,j=1}^{n} a_{ij}x_{i}x_{j} using Hölder’s inequality. This error term is shown to be a small proportion of Vec_{p}(A) for an appropriate choice of M and the exponent used in Hölder’s inequality. A careful optimization of these two parameters yields the optimal \frac{p}{e}(1 + o(1)) integrality gap. The details are presented in Section 3.

The hardness result in Theorem 1.1 is achieved via a reduction from the Unique Label Cover problem. While the reduction is similar to the one used in [5], we need to reduce from the Unique Label Cover problem (and hence use the UGC) rather than from the Label Cover problem. This complication, as well as the fact that the soundness analysis is substantially more involved, stems in essence from the following technical fact: if ∑ _{i=1}^{n} ε_{i}a_{i}, where the ε_{i} are i.i.d. symmetric Bernoulli random variables, is bounded in L_{∞} , then ∑ _{i=1}^{n} |a_{i}| is bounded, while a bound on |∑ _{i=1}^{n} a_{i}ε_{i}|^{p} does not imply a bound on ∑ _{i=1}^{n} |a_{i}| which is independent on n. This issue raises significant technical difficulties in the case of bounded p, analytic ideas that we use to overcome them might be of independent interest in the context of computational hardness results. See Section 4 for more details (specifically, the remark on the difference from the L_{∞} case on page 14).

2It should be pointed out here that this type of “static” complexity phase transition is different from another popular research direction in statistical physics—the relation between statistical phase transitions and average case hardness in random models. We refer to [1] and the references therein for more information on this topic

2 Preliminaries and notation

In this section we describe some definitions, notation, and basic facts that will be used throughout this paper. We start with a formal definition of the L_{p} Grothendieck problem, which we also call the L_{p} Quadratic Maximization problem.

Definition 2.1 (L_{p} Quadratic Maximization problem). The Quadratic Maximization problem over L_{p}, denoted QM(p) for short, is defined as follows. For a given parameter p ≥ 1 (which is possibly a function of n), an instance of the QM(p) problem is a square matrix A = (a_{ij}) ∈ ^{n×n} with zero diagonal entries. The goal is to compute

Opt_{p}(A) max { ∑_{i,j=1}^{n} a_{ij}x_{i}x_{j} : (x_{1}, …, x_{n}) ∈ ^{n} ∧ ∑_{i=1}^{n} |x_{i}|^{p} ≤ 1} .

Our hardness results will be based on the Unique Games Conjecture (see [22]). We shall now briefly present the necessary background on this topic.

In what follows, for an integer r, we denote the set {1, 2, …, r}by [r].

Definition 2.2 (Unique Label Cover problem). An instance ℒ of the Unique Label Cover problem, which we denote ULC for short, is a tuple ℒ = (V, E, r, {π_{e}}_{e∈E}), where V is a set of nodes, and E ⊆ V × V is a symmetric set of directed edges, namely if (u, w) ∈ E then also (w, u) ∈ E. For a node v ∈ V, we define d(v) to be the number of edges of the form (v, w) in E. We assume that E contains no loops, and that d(v) ≥ 1 for every v ∈ V.

For every edge e = (u, w) ∈ E a permutation π_{e} : [r] → [r] is given such that π_{(u,w)} = π_{(w,u)}^{−1} for every edge (u, w) ∈ E. A function 𝒜 : V → [r] is called an assignment for ℒ. We say that an edge e = (u, w) is satisfied by 𝒜 if 𝒜 (w) = π_{e}(𝒜 (u)). The goal in the Unique Label Cover problem is to find an assignment which maximizes the fraction of satisfied edges. We denote the maximum fraction of satisfied edges in an instance ℒ by Opt(ℒ). The number r is called the number of labels in ℒ.

Conjecture 2.3 (unique games conjecture). For any constants δ, ε > 0 satisfying δ + ε < 1 there is an integer r = r(δ, ε) such that it is NP-hard to distinguish between ULC instances ℒ with r labels for which Opt(ℒ) ≤ δ, and instances with r labels for which Opt(ℒ) ≥ 1 − ε.

As noted in the introduction, the unique games conjecture was put forth by Khot in [22], and it is a commonly used complexity assumption. Despite some recent works that tried to refute it (see the table in [14] for a description of the known results), the unique games conjecture still stands. Moreover, even the following stronger hypothesis has not been contradicted by any result so far.

Hypothesis 2.4 (The strong unique games hypothesis). There are positive constants c_{1}, c_{2}, c_{3} for which it is NP-hard to distinguish between ULC instances ℒ of size n with c_{1} logn labels for which Opt(ℒ) ≤ \frac{c_{2}}{logn}, and instances with c_{1} logn labels for which Opt(ℒ) ≥ 1 − \frac{c_{3}}{\sqrt{logn}}.

We shall now record some moment bounds for Gaussian random variables and sums of independent random variables. These bounds will be used extensively in what follows.

Let g be a standard Gaussian random variable. Recall that we denote its p’th moment by γ_{p}, i.e. γ_{p} ( |g|^{p})^{1/p}. Then

γ_{p}^{p} = \frac{2}{\sqrt{2π}} ∫ _{0}^{∞} x^{p}e^{−x^{2}/2}dx (x= \sqrt{2t}) ; = \frac{2^{p/2}}{\sqrt{π}} ∫ _{0}^{∞} t^{\frac{p+1}{2} −1}e^{−t}dt = \frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}}.

The following version of Stirling’s formula [6],

\sqrt{\frac{2π}{x}} · (\frac{x}{e})^{x} ≤ Γ(x) ≤ \sqrt{\frac{2π}{x}} · (\frac{x}{e})^{x}e^{\frac{1}{12x}},

implies that

γ_{p}^{p} ∈ [\sqrt{\frac{2}{e}} (\frac{p + 1}{e} )^{p/2}, \sqrt{\frac{2}{e}} (\frac{p + 1}{e} )^{p/2}e^{\frac{1}{6(p+1)}} ].  (3)

In fact the following stronger lower bound holds true for p > 2 (This bound is optimal in terms of the second order terms as p → 2 and p → ∞. Since we will not use it here, we shall not include its elementary, though tedious, proof):

γ_{p}^{2} ≥ max\{1 + (1 − \frac{γ + ln2}{2} ) (p − 2), \frac{p}{e} + \frac{ln2}{e}\} ,  (4)

where γ = 0.5772... is Euler’s constant.

Lemma 2.5. Let X_{1}, …, X_{n} be independent random variables such that X_{j} = 0 and ∑ _{j=1}^{n} X_{j}^{2} = 1. Assume also that for some δ ∈ (0, e^{−4})we have ∑ _{j=1}^{n} |X_{j}|^{3} < δ. Then for every p ≥ 1,

( |∑_{j=1}^{n} X_{j} |^{p})^{1/p} ≥ γ_{p} · (1 − 4 (log(1/δ))^{p/2}δ) .

Proof. By the Berry-Esseen theorem (see [19]. The constant we use below follows from [32]), for every u > 0 we have

Pr (|∑_{j=1}^{n} X_{j} |≥ u) ≥ Pr(|g| ≥ u) − 2 ∑_{j=1}^{n} |X_{j}|^{3} ≥ Pr(|g| ≥ u) − 2δ.

Therefore, for every a > 0 we have

|∑_{j=1}^{n} X_{j} |^{p} = ∫ _{0}^{∞} pu^{p−1} Pr (|∑_{j=1}^{n} X_{j} |≥ u)du ≥ ∫ _{0}^{a} pu^{p−1} Pr(|g| > u)du − 2δa^{p}

≥ \sqrt{\frac{2}{π}} ∫ _{0}^{a} u^{p}e^{−u^{2}/2}du − 2δa^{p} = γ_{p}^{p} − \sqrt{\frac{2}{π}} ∫ _{a}^{∞} u^{p}e^{−u^{2}/2}du − 2δa^{p}. (5)

Choosing a = γ_{p} \sqrt{log(1/δ)}yields the required result, where we use the bound ∫_{a}^{∞} u^{p}e^{−u^{2}/2}du ≤ 2a^{p−1}e^{−a^{2}/2}, which holds whenever a^{2} > 2p—this estimate follows from the inequality

∫ _{a}^{∞} u^{p}e^{−u^{2}/2}du = a^{p−1}e^{−a^{2}/2} + (p − 1) ∫ _{a}^{∞} u^{p−2}e^{−u^{2}/2}du ≤ a^{p−1}e^{−a^{2}/2} + \frac{p − 1}{a^{2}} ∫ _{a}^{∞} u^{p}e^{−u^{2}/2}du.

The proof of Lemma 2.5 is complete.

For large p we will need a better bound, which is contained in the following lemma. Recall that a random variable X is symmetric if X and −X have the same distribution.

Lemma 2.6. Let X_{1}, …, X_{n} be independent symmetric random variables such that ∑ _{j=1}^{n} X_{j}^{2} = 1. Fix p ≥ 2

and assume that max_{1≤j≤n} \sqrt{X_{j}^{2}} ≤ \frac{2}{p}. Then

( |∑_{j=1}^{n} X_{j} |^{p})^{1/p} ≥ \sqrt{\frac{p}{e}} − \frac{2}{\sqrt{p}}.

Proof. Let k ∈ be the largest integer such that 2k ≤ p. Denote a_{j} \sqrt{X_{j}^{2}}, so that ∑ _{j=1}^{n} a_{j}^{2} = 1, and

write δ max_{1≤j≤n} |a_{j}| ≤ \frac{2}{p} ≤ \frac{1}{k}. Note that

(∑_{j=1}^{n} X_{j} )^{2k} = ∑_{\begin{matrix}ℓ_{1},...,ℓ_{n}∈ ∪\{0\} \\ ℓ_{1}+··· +ℓ_{n}=k \end{matrix}} \frac{(2k)!}{∏ _{j=1}^{n} (2ℓ_{j})!} ∏_{j=1}^{n} X_{j}^{2ℓ_{j}} ≥ \frac{(2k)!}{2^{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}∏_{j∈S} a_{j}^{2}.  (6)

On the other hand

1 = (∑_{j=1}^{n} a_{j}^{2})^{k}

= ∑_{\begin{matrix}ℓ_{1},...,ℓ_{n}∈ ∪\{0\} \\ ℓ_{1}+··· +ℓ_{n}=k \end{matrix}} \frac{k!}{∏ _{j=1}^{n} ℓ_{j}!} ∏_{j=1}^{n} a_{j}^{2ℓ_{j}}

≤ k! ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}∏_{j∈S} a_{j}^{2} + ∑_{j=1}^{n} a_{j}^{2} ∑_{\begin{matrix}r_{1},...,r_{n}∈ ∪\{0\} \\ r_{1}+··· +r_{n}=k−1 \\ r_{j}≥1 \end{matrix}} \frac{k}{r_{j} + 1} · \frac{(k − 1)!}{∏ _{i=1}^{n} r_{i}!} ∏_{i=1}^{n} a_{i}^{2r_{i}}

≤ k! ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}∏_{j∈S} a_{j}^{2} + \frac{kδ^{2}}{2} ∑_{\begin{matrix}r_{1},...,r_{n}∈ ∪\{0\} \\ r_{1}+··· +r_{n}=k−1 \end{matrix}} |\{1 ≤ j ≤ n : r_{j} ≥ 1\}| \frac{(k − 1)!}{∏ _{i=1}^{n} r_{i}!} ∏_{i=1}^{n} a_{i}^{2r_{i}}

≤ k! ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}∏_{j∈S} a_{j}^{2} + \frac{k(k − 1)δ^{2}}{2} ∑_{\begin{matrix}r_{1},...,r_{n}∈ ∪\{0\} \\ r_{1}+··· +r_{n}=k−1 \end{matrix}} \frac{(k − 1)!}{∏ _{i=1}^{n} r_{i}!} ∏_{i=1}^{n} a_{i}^{2r_{i}}

= k! ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}∏_{j∈S} a_{j}^{2} + \frac{k(k − 1)δ^{2}}{2} (∑_{j=1}^{n} a_{j}^{2})^{k−1}

= k! ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}∏_{j∈S} a_{j}^{2} + \frac{k(k − 1)δ^{2}}{2}.

Hence,

∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}∏_{j∈S} a_{j}^{2} ≥ \frac{1 − \frac{k(k−1)δ^{2}}{2}}{k!} ≥ \frac{1}{2k!}.  (7)

Combining (7) with (6) we get that

( |∑_{j=1}^{n} X_{j} |^{p})^{\frac{1}{p}} ≥ ( (∑_{j=1}^{n} X_{j} )^{2k})^{\frac{1}{2k}} ≥ (\frac{(2k)!}{2^{k+1}k!})^{\frac{1}{2k}} ≥ \sqrt{\frac{2k}{e}} − \frac{1}{4 \sqrt{k}} ≥ \sqrt{\frac{p}{e}} − \frac{2}{\sqrt{p}},

where we used Stirling’s formula and the fact that p ≥ 2k ≥ p − 2.

3 A \frac{p}{e} (1 + o(1)) approximation algorithm for QM(p)

Let A = (a_{ij}) ∈ M_{n}( ) be an n × n matrix with zeros on the diagonal and fix p ≥ 2. Recall that

Opt_{p}(A) = max { ∑_{i,j=1}^{n} a_{ij}x_{i}x_{j} : {x_{1}, …, x_{n}} ⊆ ∧ ∑_{i=1}^{n} |x_{i}|^{p} ≤ 1},  (8)

We define the following parameter:

Vec_{p}(A) max { ∑_{i,j=1}^{n} a_{ij}⟨v_{i}, v_{j}⟩ : {v_{1}, …, v_{n}} ⊆ L_{2} ∧ ∑_{i=1}^{n} ∥v_{i}∥_{2}^{p} ≤ 1} .  (9)

Claim 3.1. There is a PTAS for computing Vec_{p}(A).

Proof. Let P_{n} denote the space of all n × n matrices P ∈ M_{n}( ) which are positive semidefinite. We also write K {(m_{ij}) ∈ M_{n}( ) : ∑ _{i=1}^{n} |m_{ii}|^{p/2} ≤ 1}. Since p ≥ 2 the set K is convex. Moreover, K has a polynomial time membership oracle (more generally, any body given by ∑ _{i=1}^{n} f (|m_{ii}|) ≤ 1, where f is convex and computable, has polynomial time membership oracle). It follows from the Grötschel-Lovász-Schrijver convex optimization theory [18] that there is a PTAS for computing the maximum of the linear functional ∑ _{i,j=1}^{n} a_{ij}m_{ij} on P_{n} ∩ K. This maximum is precisely Vec_{p}(A).

Theorem 3.2. We have the following inequality:

Opt_{p}(A) ≤ Vec_{p}(A) ≤ (\frac{p}{e} + 30 logp) · Opt_{p}(A).

Therefore there is a polynomial time algorithm which computes Opt_{p}(A) up to a factor of (\frac{p}{e} + 30 logp).

Proof. The left hand inequality in Theorem 3.2 is obvious. As is often the case with Grothendieck-type inequalities, we will work with the Gaussian Hilbert Space—this approach to Grothendieck’s inequality first appeared in print in a paper of Johnson and Lindenstrauss [21], and was used extensively in [4, 3]. Let g_{1}, g_{2}, …be i.i.d. standard Gaussian random variables, and assume that they are defined on some probability space (Ω, Pr). The Gaussian Hilbert space H is the closure in L_{2}(Ω) of the linear span of {g_{1}, g_{2}, ...}. By the definition of Vec_{p}(A) (and a simple compactness argument) there are h_{1}, …, h_{n} ∈ H such that

∑_{i=1}^{n} ( h_{i}^{2})^{p/2} ≤ 1 and ∑_{i,j=1}^{n} a_{ij}h_{i}h_{j} = Vec_{p}(A).

Fix M > 1 which will be determined later, and consider the event

S \{∑_{i=1}^{n} |h_{i}|^{p} > M · \frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}} \}.  (10)

The crucial point to note here is that since each h_{i} is a Gaussian random variable we have the identity |h_{i}|^{p} = γ_{p}^{p} ( h_{i}^{2})^{p/2}. Markov’s inequality implies that

Pr[S] ≤ \frac{∑ _{i=1}^{n} |h_{i}|^{p}}{M · ^{\frac{2^{p/2}Γ(\frac{p+1}{2} )}{\sqrt{π}}}} ≤ \frac{1}{M} ∑_{i=1}^{n} ( h_{i}^{2})^{p/2} ≤ \frac{1}{M}.  (11)

Now (11), and an application of Hölder’s inequality, implies that for every q > 1,

B ∑_{i=1}^{n} ( (h_{i}1_{S})^{2})^{p/2} ≤ ∑_{i=1}^{n} ( h_{i}^{2q})^{\frac{p}{2q}} (Pr[S])^{\frac{p(q−1)}{2q}} ≤ ∑_{i=1}^{n} (\frac{2^{q}Γ (q + \frac{1}{2})}{\sqrt{π}} ( h_{i}^{2})^{q})^{\frac{p}{2q}} \frac{1}{M^{\frac{p(q−1)}{2q}}}

= (\frac{2^{q}Γ (q + \frac{1}{2})}{M^{q−1} \sqrt{π}} )^{\frac{p}{2q}} ∑_{i=1}^{n} ( h_{i}^{2})^{p/2} ≤ (\frac{2^{q}Γ (q + \frac{1}{2})}{M^{q−1} \sqrt{π}} )^{\frac{p}{2q}} .

Hence, an application of the definition of Vec_{p}(A) to the vectors \frac{h_{i}1_{S}}{B^{1/p}} ∈ L_{2}(Ω) implies that

∑_{i,j=1}^{n} a_{ij}h_{i}h_{j}1_{S} ≤ B^{2/p}Vec_{p}(A) ≤ (\frac{2^{q}Γ (q + \frac{1}{2})}{M^{q−1} \sqrt{π}} )^{1/q} · Vec_{p}(A).  (12)

On the other hand, the definition of Opt_{p}(A) implies that

∑_{i,j=1}^{n} a_{ij}h_{i}h_{j}1_{Ω\S} = (M · \frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}} )^{2/p} ∑_{i,j=1}^{n} a_{ij} \frac{h_{i}}{(M · ^{\frac{2^{p/2}Γ(\frac{p+1}{2} )}{\sqrt{π}}})_{1/p}} · \frac{h_{j}}{(M · ^{\frac{2^{p/2}Γ(\frac{p+1}{2} )}{\sqrt{π}}})_{1/p}}1_{Ω\S}

≤ (M · \frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}} )^{2/p}Opt_{p}(A). (13)

Combining (12) and (13) we get that

Vec_{p}(A) = ∑_{i,j=1}^{n} a_{ij}h_{i}h_{j} = ∑_{i,j=1}^{n} a_{ij}h_{i}h_{j}1_{S} + ∑_{i,j=1}^{n} a_{ij}h_{i}h_{j}1_{Ω\S}

≤ (\frac{2^{q}Γ (q + \frac{1}{2})}{M^{q−1} \sqrt{π}} )^{1/q} · Vec_{p}(A) + (M · \frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}} )^{2/p}Opt_{p}(A). (14)

The right-hand side of (14) is mimimized for

M = (\frac{p(q − 1)}{2q} · (\frac{2^{q}Γ (q + \frac{1}{2})}{\sqrt{π}} )^{1/q} · (\frac{\sqrt{π}}{2^{p/2}Γ (\frac{p+1}{2} )} )^{2/p} · \frac{Vec_{p}(A)}{Opt_{p}(A)})^{\frac{pq}{pq+2q−p}} .  (15)

Plugging this value of M into (14) we get the inequality

Vec_{p}(A) ≤ [Vec_{p}(A)]^{\frac{2q}{pq+2q−p}} · [Opt_{p}(A)]^{\frac{p(q−1)}{pq+2q−p}}

· (\frac{2^{q}Γ (q + \frac{1}{2})}{\sqrt{π}} )^{\frac{2}{pq+2q−p}} (\frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}} )^{\frac{2(q−1)}{pq+2q−p}} [(\frac{2q}{p(q − 1)} )^{\frac{p(q−1)}{pq+2q−p}} + (\frac{p(q − 1)}{2q} )^{\frac{2q}{pq+2q−p}} ] ,

which simplifies to give the bound,

\frac{Vec_{p}(A)}{Opt_{p}(A)} ≤ (\frac{2^{p/2}Γ (\frac{p+1}{2} )}{\sqrt{π}} )^{2/p} · (\frac{2^{q}Γ (q + \frac{1}{2})}{\sqrt{π}} )^{\frac{2}{p(q−1)}} [(\frac{2q}{p(q − 1)} )^{\frac{p(q−1)}{pq+2q−p}} + (\frac{p(q − 1)}{2q} )^{\frac{2q}{pq+2q−p}} ]^{1+ \frac{2q}{p(q−1)}} . (16)

Choosing q = 2 in (16), and using the bounds in (3), yields the required result. But, if we optimize over q we get better bounds. This yields in particular much better approximation factors for small p. For large p the correct choice of q is q = Θ(logp), and the bound that we get becomes

Vec_{p}(A) ≤ (\frac{p}{e} + \frac{2}{e} logp + \frac{2}{e} loglogp + O (1)) Opt_{p}(A).

In any case, the proof of Theorem 3.2 is complete.

Remark 3.3. As described in the introduction, the above algorithm does not only compute an approximation to Opt_{p}(A)—it also rounds the vectors v_{1}, …, v_{n} ∈ ^{n} for which Vec_{p}(A) is approximately attained to scalars x_{1}, …, x_{n} satisfying ∑ _{i=1}^{n} |x_{i}|^{p} ≤ 1 and ∑ _{i,j=1}^{n} a_{ij}x_{i}x_{j} ≤ (\frac{p}{e} + 30 logp) · Opt_{p}(A). Indeed, we can concretely realize the Gaussians h_{i} that appeared in the proof of Theorem 3.2 as h_{i} = ⟨v_{i}, G⟩, where G is a standard Gaussian vector in ^{n}. We then define x_{i} \frac{1}{M̃^{1/p}}⟨v_{i}, G⟩1_{Ω\S} , where analogously to (15),

M̃ = (\frac{p(q − 1)}{2q} · (\frac{2^{q}Γ (q + \frac{1}{2})}{\sqrt{π}} )^{1/q} · (\frac{\sqrt{π}}{2^{p/2}Γ (\frac{p+1}{2} )} )^{2/p} · (\frac{p}{e} + 30 logp) )^{\frac{pq}{pq+2q−p}} ,

q ≈ logp and S is as in (10). By repeating the argument in the proof of Theorem 3.2 with the value M̃ instead of the value M in (15), i.e. by replacing the term \frac{Vec_{p}(A)}{Opt_{p}(A)} in the definition of M with its a priori bound which we already proved, shows that this rounding procedure yields the desired approximation factor.

4 UGC hardness

In this section we will make use of the notation and definitions in Section 2. We also require the following definition.

Definition 4.1. For p ≥ 2 and ε > 0 let ϕ(p, ε) be the smallest ϕ > 0 such that for all n ∈ if (a_{1}, …, a_{n}) ∈ n satisfy ∑ _{i=1}^{n} a_{i}^{2} = 1 and max_{i∈[n]}a_{i}^{2} ≤ ϕ then

( |∑_{i=1}^{n} a_{i}ε_{i}|^{p})^{1/p} ≥ (1 − ε)γ_{p},

where ε_{1}, …, ε_{n} are i.i.d. symmetric ±1 Bernoulli random variables. The existence of ϕ(p, ε) follows from Lemma 2.5. Moreover, Lemma 2.6, combined with (3) implies that

ϕ (p, \frac{10}{p}) ≤ \frac{4}{p^{2}}.  (17)

It will be convenient to introduce the following notation. Given p ≥ 1 and a function f : X → defined on a finite set X, we write _{x∈X}f (x) \frac{1}{|X|}∑ _{x∈X}f (x) and ∥f ∥_{p} ( _{x∈X}|f (x)|^{p})^{1/p} (thus in what follows L_{p} norms will correspond exclusively to uniform distributions on finite sets). If μ is a probability distribution μ on X then we use the notation _{x∼μ}f (x) ∫_{X}f (x)dμ(x).

The main result of this section is the following reduction.

Theorem 4.2. There exists a reduction algorithm from ULC to QM(p) which, given a ULC instance ℒ = (V, E, r, {π_{e}}_{e∈E}), outputs an instance A of QM(p). The reduction algorithm runs in time polynomial in |V| and 2^{r}, and has the following properties:

• Completeness: Opt_{p}(A) ≥ Opt(ℒ) − \frac{1}{|V|}

• Soundness: For every ε > 0 it holds that

Opt_{p}(A) ≤ (\frac{4γ_{p}^{12}}{ε^{4}ϕ(p, ε)^{2}} · Opt(ℒ))^{(p−2)/p} + \frac{1 + 2ε + 3/ |V|}{(1 − ε)γ_{p}^{2}} + \frac{1}{|V|}.  (18)

The proof of Theorem 4.2 spans the rest of this section, but before we commence with it, let us prove a corollary that follows from it if we assume the unique games conjecture, and one that follows if we assume the strong unique games hypothesis.

Corollary 4.3. Let p > 2 be any constant, and let δ > 0 be a constant such that (1−δ)γ_{p}^{2} > 1. Then assuming the unique games conjecture, it is NP-hard to approximate QM(p) within a factor (1 − δ)γ_{p}^{2}. Using (4) it follows that assuming the unique games conjecture it is NP-hard to approximate QM(p) within a factor \frac{p}{e} + \frac{1}{4} (note that we are using a crude, sub-optimal in terms of the additive constant term, version of (4) here).

Proof. Set ε′ = ε = δ/8, and pick δ′ > 0 small enough so that d′ < 1 − ε′and

(\frac{4γ_{p}^{12}}{ε^{4}ϕ(p, ε)^{2}} · δ′)^{(p−2)/p} ≤ \frac{δ}{4γ_{p}^{2}}.

From the unique games conjecture we have that there exists an integer r, such that it is NP-hard to distinguish between instances ℒ of ULC with r labels for which Opt(ℒ) ≥ 1 − ε′, and instances with r labels for which Opt(ℒ) ≤ δ′. The reduction stated in Theorem 4.2 maps instances ℒ of the first kind into QM(p) instances A with Opt_{p}(A) ≥ 1 − ε′− 1/|V| = 1 − δ/8 − 1/|V| (note that the reduction runs in polynomial time). We call such instances ‘yes’ instances.

By the soundness property, it maps instances ℒ of the latter kind into instances A satisfying

Opt_{p}(A) ≤ \frac{δ}{4γ_{p}^{2}} + \frac{1 + 2ε + 3/|V|}{(1 − ε)γ_{p}^{2}} + \frac{1}{|V|}≤ \frac{δ}{4γ_{p}^{2}} + \frac{1 + δ/2 + 3/|V|}{γ_{p}^{2}}+ \frac{1}{|V|}.

These are called ‘no’ instances.

Thus the ratio between the values of Opt_{p}(A) for ‘yes’ and for ‘no’ instances tends, as |V| goes to infinity, to a number which is greater than (1 − δ)γ_{p}^{2}. This completes the proof of Corollary 4.3.

Corollary 4.4. Let p = p(n) be a parameter such that p(n) = o ((logn)^{\frac{1}{32}}). Then assuming the strong unique games hypothesis, it is NP-hard to approximate QM(p) within a factor \frac{p}{e} − O(1).

Proof. This is proved similarly to Corollary 4.3, using δ = 100/p and using Hypothesis 2.4 instead of the unique games conjecture. Also, when following the proof of Corollary 4.3, one should use the bound from (17) so that the value needed for δ′is not smaller than \frac{c_{2}}{logn}, where c_{2} is as in Hypothesis 2.4.

4.1 The reduction

Let us begin by describing the reduction algorithm. Let ℒ = (V, E, r, {π_{e}}_{e∈E}) be an instance of ULC. The reduction will make use of the following parameters:

D |V|^{3} · |E|· 2^{2r}  and  B |V|^{2} · |E|· 2^{2r}.  (19)

Some notation. Given ℒ, the reduction should output a square matrix A with zero diagonal entries. Equivalently, we prefer to think of the output of the reduction as a multilinear form defined on vectors F, and to write A(F) instead of ⟨AF, F⟩ (multilinearity, i.e. linearity in each of the coordinates of the vector, is equivalent in matrix notation to A having zero entries on the diagonal).

The coordinates. It will be convenient to use meaningful indices for the coordinates of F. For every node v ∈ V there will be D · d(v) sets of coordinates {C_{v}^{j}}_{j∈[D·d(v)]}. Each such set C_{v}^{j} will contain 2^{r} coordinates,

labeled {C_{v}^{j}(x)}_{x∈{−1,1}^{r}}. These coordinates serve as encodings of assignments for v: For F to encode the assignment i for v, it should satisfy

∀ j ∈ [D · d(v)], ∀x ∈ {−1, 1}^{r} F_{C_{v}^{j}(x)} = x_{i}.

Given a vector F with coordinates indexed as above, we define a function f_{v}^{j} : {−1, 1}^{r}→ for every v ∈ V and j ∈ [D · d(v)], by setting

f_{v}^{j}(x) = F_{C_{v}^{j}(x)}

(for simplicity of notation, we keep the dependency of f_{v}^{j} on F implicit). We also define for every v ∈ V a function f_{v} : {−1, 1}^{r}→ by taking

f_{v}(x) _{j∈[D·d(v)]}[f_{v}^{j}(x)] .  (20)

The distribution μ. Before we proceed to define the value of the multilinear form A on F, let us note that for every q ≥ 1 we can write the L_{q} norm of a vector F as follows. Let μ be the probability distribution on V defined by μ(v) \frac{d(v)}{|E|} (recall that we defined d(v) to be just the outgoing degree of v, and therefore this really is a probability distribution). Then for every q ≥ 1,

∥F∥_{q} = ( _{v∼μ} _{j∈[D·d(v)]}∥f_{v}^{j} ∥_{q}^{q}) ^{1/q}.  (21)

Equation (21) follows directly from the definition of the functions f_{v}^{j}. Since q ≥ 1, it now follows from the triangle inequality in L_{q} and from (20) that

( _{v∼μ}∥f_{v}∥_{q}^{q})^{1/q} ≤ ∥F∥_{q}.  (22)

The inner and outer forms. We are ready to define the quadratic form A. Although A is defined over the coordinates of the vector F, it will be easier to describe it as a form over the Fourier coefficients of the functions {f_{v}}_{v∈V}. Such a quadratic form is also a quadratic form over F since each of these coefficients can be written as a linear combination of the coordinates of F. We shall deal with the multilinearity of the form later.

The form A will be a sum of two terms, one called the inner term and the other, the outer term. The inner term will serve to prevent A from taking large values unless the functions {f_{v}}_{v∈V}associated with F are very close to being linear homogeneous. The role of the outer term is, roughly, to allow A to obtain large values on vectors F which encode assignments for ℒ that satisfy a large fraction of the edges.

For each v ∈ V, we define a quadratic form A_{v} on F by

A_{v}(F) −B · ∑_{\begin{matrix}S⊆[r] \\ |S| 1 \end{matrix}} f̂_{v}(S)^{2}.

We take the inner term to be

A_{inner}(F) _{v∼μ} [A_{v}(F)].

For every edge e = (u, w) ∈ E we let

A_{e}(F) ∑_{i∈[r]} f̂_{u}(i)f̂_{w}(π_{e}(i)),

and define the outer term to be

A_{outer} _{e∈E} [A_{e}(F)].

The quadratic form. We define A′(F) = A_{inner}(F) + A_{outer}(F). We would have liked to take A′ as the output of the reduction algorithm, but it turns out to have some non-multilinear terms (i.e. some non-zero diagonal entries in matrix language). For simplicity of analysis, we therefore first establish the completeness and soundness properties for A′as it is defined here. In Subsection 4.4 we slightly change A′to remove the diagonal entries, obtaining the final quadratic form A, and show that for every vector F with ∥F∥_{p} ≤ 1,

|A′(F) − A(F)| ≤ \frac{1}{|V|}.  (23)

Running time. It is obvious from the construction that the form A′can be constructed in time polynomial in |V|and in 2^{r} as required. This will also hold for the actual form A, that is defined in Subsection 4.4.

Our next step is to establish, in the next two subsections, the completeness and soundness properties of A′, and therefore, assuming (23), also of A.

4.2 Completeness

To get the completeness property we start with an assignment 𝒜 : V → [r] for ℒ which satisfies an Opt(ℒ) fraction of the edges, and use is to get a vector F with ∥F∥_{p} ≤ 1 such that A′(F) = Opt(ℒ). Assuming (23), this gives the completeness property.

The vector F. We define F by

∀ v ∈ V, ∀ j ∈ [D · d(v)], ∀ x ∈ {−1, 1}^{r}, F_{C_{v}^{j}(x)} = x_{𝒜 (v)} .

It is clear that ∥F∥_{p} = 1, since all of its coordinates are either 1 or −1, and that the functions {f_{v}}_{v∈V}associated with F satisfy

∀ v ∈ V, x ∈ {−1, 1}^{r},  f_{v}(x) = x_{𝒜 (v)} .  (24)

The functions f_{v} are therefore linear, which implies that A_{inner}(F) = 0. It also follows from (24) that for every edge e ∈ E, the value of A_{e}(F) is 1 if 𝒜 satisfies e and 0 otherwise, and therefore

A_{outer}(F) = e ∈ E [A_{e}(F)]= Pr_{e∈E}[𝒜 satisfies e] = Opt(ℒ).

Overall, we thus have A′(F) = A_{inner}(F) + A_{outer}(F) = Opt(ℒ), as desired.

4.3 Soundness

To establish the soundness property, let F be any vector with ∥F∥_{p} ≤ 1. We shall prove that

A′(F) ≤ (\frac{4γ_{p}^{12}}{ε^{4}ϕ(p, ε)^{2}} · Opt(ℒ))^{(p−2)/p} + \frac{1 + 2ε + 3/ |V|}{(1 − ε)γ_{p}^{2}},  (25)

and then the soundness property will follow from (25)together with (23). We assume w.l.o.g. that A′(F) ≥ 0.

Our aim is to use the vector F to define an assignment for ℒ, which will prove that Opt(ℒ) is large enough to make (25) hold.

On the difference between the L_{p} case and the L_{∞} case. Our definition of the assignment for ℒ is different than that in [5]. In that paper every v ∈ V was given a multi-assignment by taking all the elements i ∈ [r] for which |f̂_{v}(i)| was greater than a certain threshold. The assignment for v was then chosen randomly from among the elements of its multi-assignment. Since in [5] the L_{∞} norm of F was bounded by 1, it was possible there to get a bound on ∑ _{i=1}^{n} |f̂_{v}(i)|, and therefore on the size of the multi-assignment (using the fact that the L_{∞} norm of a linear function f equals ∑ _{i=1}^{n} |f̂(i)|). Since here we only have a bound on the L_{p} norm of F, that approach does not work and the definition of the multi-assignment, as well as its analysis, are more involved.

Before we define the assignment for ℒ we make the following definitions and observations.

Claim 4.5. Suppose that a real number t_{v} is associated with every node v ∈ V. Then

e=(u,w)∈E [t_{u}t_{w}]≤ _{v∼μ} [|t_{v}|^{2}].  (26)

Proof. Consider the set of pairs {(v, j)}_{v∈V, j∈[d(v)]}as a set of indices, and define a vector X by X_{(v,j)} = t_{v}. Then the r.h.s. of (26) equals ∥X∥_{2}^{2}. The l.h.s. of (26) is the inner product of X with a vector whose coordinates are simply a permutation of the coordinates of X (this follows from the fact that E is symmetric). Hence (26) follows from the Cauchy-Schwarz inequality.

The following claim follows by the same argument as in Claim 4.5.

Claim 4.6. Let S ⊆ E be a symmetric subset (that is, if (u, w) ∈ S then also (w, u) ∈ S), and let {t_{v}}_{v∈V} be any real numbers. Then

∑_{(u,w)∈S}t_{u}t_{w} ≤ ∑_{(u,w)∈S}|t_{u}|^{2}.

The linear part of the functions f_{v} play an important role later on. Let us set a notation for them.

Definition 4.7. For every v ∈ V, let f_{v}^{l}denote the linear homogeneous part of f_{v}, namely f_{v}^{l}(x) = ∑ _{i∈[r]} f̂_{v}(i)x_{i}. Let f_{v}^{h} = f_{v} − f_{v}^{l}.

We next establish some properties of the functions f_{v}^{l} and f_{v}^{h}.

Claim 4.8. max_{v∈V, x∈\{−1,1\}^{r}}(|f_{v}^{h}(x)|)≤ 2^{r} · \sqrt{\frac{|E|}{B}} = \frac{1}{|V|}.

Proof. First, note that

A_{outer}(F)= _{e=(u,w)∈E} [∑_{i∈[r]} f̂_{u}(i)f̂_{w}(π_{e}(i))]
≤ _{e=(u,w)∈E} [∥f_{u}∥_{2}∥f_{w}∥_{2}]  (Cauchy-Schwarz)
≤ _{v∼μ} [∥f_{v}∥_{2}^{2}] ≤ ∥F∥_{2}^{2}  by Claim 4.5 and by (22)
≤ ∥F∥_{p}^{2} ≤ 1.

Hence, since we assumed that A′(F) ≥ 0, we have from the definition of A_{inner}, μ, and the functions f_{v}^{h} that

−1 ≤ A_{inner}(F) = −B · _{v∼μ} [∥f_{v}^{h}∥_{2}^{2}] = −B · \frac{∑ _{v∈V}d(v)∥f_{v}^{h}∥_{2}^{2}}{|E|}.

It follows that

max_{v∈V}(∥f_{v}^{h}∥_{1}^{2}) ≤ max_{v∈V}(∥f_{v}^{h}∥_{2}^{2}) ≤ \frac{|E|}{B},

and therefore that

max_{v∈V, x∈\{−1,1\}^{r}}(|f_{v}^{h}(x)|)≤ 2^{r} max_{v∈V}(∥f_{v}^{h}∥_{1}) ≤ 2^{r} · \sqrt{\frac{|E|}{B}} = \frac{1}{|V|},

where the last equality follows from the definition of B (19). This completes the proof of the claim.

Claim 4.9. [ _{v∼μ} ∥f_{v}^{l}∥_{p}^{p}]^{1/p} ≤ 1 + \frac{1}{|V|}.

Proof. Using the triangle inequality in L_{p} we have

[ _{v∼μ} ∥f_{v}^{l}∥_{p}^{p}]^{1/p} ≤ [ _{v∼μ}∥f_{v}∥_{p}^{p}]^{1/p} + [ _{v∼μ} ∥f_{v}^{h}∥_{p}^{p}]^{1/p} ≤^{(22)} ∥F∥_{p} + max_{v∈V, x∈\{−1,1\}^{r}}(|f_{v}^{h}(x)|) ≤ 1 + \frac{1}{|V|},

where the last inequality follows from Claim 4.8 and the assumption that ∥F∥_{p} ≤ 1.

Influential coordinates. We now identify the influential coordinates in the functions f_{v}^{l}, which will serve as the basis for getting an assignment for ℒ. For this purpose, we pick the parameters

a \frac{γ_{p}^{2}}{ϕ(p, ε)}  and  b \frac{γ_{p}^{4} · a}{ε^{2}},

where ϕ(p, ε) is as in Definition 4.1. We define for every v ∈ V subsets α(v), β(v), γ(v) ⊆ [r] as follows: α(v) is taken to be the set of size a of coordinates i ∈ [r] for which |f̂_{v}(i)| is largest (ties are broken arbitrarily). β(v) is taken to be the set of b coordinates^{3} with the largest values of |f̂_{v}(i)| among [r] \ α(v), and γ(v) is defined by γ(v) = [r] \ (α(v) ∪ β(v)).

For every v ∈ V, define f_{v}^{α}(x) ∑ _{i∈α(v)} f̂_{v}(i)x_{i}, f_{v}^{β}(x) ∑ _{i∈β(v)} f̂_{v}(i)x_{i}, f_{v}^{γ}(x) ∑ _{i∈γ(v)} f̂_{v}(i)x_{i}. So that f_{v}^{α} + f_{v}^{β} + f_{v}^{γ} = f_{v}^{l}.

The assignment for ℒ. We view the sets {α(v) ∪ β(v)}_{v∈V}as a multi-assignment for ℒ, namely an assignment of several values for each v ∈ V. We say that an edge e = (u, w) ∈ E is satisfied by the multi-assignment if there exists an i ∈ α(u) ∪ β(u) such that π_{e}(i) ∈ α(w) ∪ β(w). We define S ⊆ E to be the set of edges that are satisfied by the multi-assignment. Note that S is a symmetric set.

We use the multi-assignment to choose a random assignment 𝒜 for ℒ, choosing 𝒜 (v) to be a uniformly distributed element in α(v) ∪ β(v). In this case, each edge e ∈ S is satisfied by 𝒜 with probability at least (\frac{1}{a+b})^{2}, and therefore

\frac{|S|}{|E|} ≤ (a + b)^{2} · Opt(ℒ).  (27)

Bounding A’(F). We are now ready to bound A′(F). We first bound it by a sum of several terms, and then bound each term separately.

A′(F) ≤ A_{outer}(F) = _{e=(u,w)∈E} [∑_{i∈[r]} f̂_{u}(i)f̂_{w}(π_{e}(i))]

= _{e=(u,w)∈E} [ ∑_{\begin{matrix}i∈α(u)∪β(u) \\ π_{e}(i)∈α(w)∪β(w) \end{matrix}} f̂_{u}(i)f̂_{w}(π_{e}(i))]  (28)

+ _{e=(u,w)∈E} [ ∑_{\begin{matrix}i∈α(u) \\ π_{e}(i)∈γ(w) \end{matrix}} f̂_{u}(i)f̂_{w}(π_{e}(i))]+ _{e=(u,w)∈E} [ ∑_{\begin{matrix}i∈γ(u) \\ π_{e}(i)∈α(w) \end{matrix}} f̂_{u}(i)f̂_{w}(π_{e}(i))]  (29)

+ _{e=(u,w)∈E} [ ∑_{\begin{matrix}i∈β(u) \\ π_{e}(i)∈γ(w) \end{matrix}} f̂_{u}(i)f̂_{w}(π_{e}(i))]+ _{e=(u,w)∈E} [ ∑_{\begin{matrix}i∈γ(u) \\ π_{e}(i)∈α(w) \end{matrix}} f̂_{u}(i)f̂_{w}(π_{e}(i))].  (30)

We use the following lemmas to bound the above terms.

Lemma 4.10. (28) ≤ ((a + b)^{2} · Opt(ℒ))^{(p−2)/p}.

3To be precise, we should have take the size of α(v) and β(v) to be ⌈a⌉ and ⌈b⌉ respectively. However for simplicity we disregard this minor issue.

Lemma 4.11. (29) ≤ 2 · \sqrt{\frac{a}{b}} = \frac{2ε}{γ_{p}^{2}}.

Lemma 4.12. (30) ≤ \frac{1 + 3/ |V|}{(1 − ε)γ_{p}^{2}}.

Using the bounds from Lemma 4.10, Lemma 4.11, and Lemma 4.12, and substituting the values of a and b, we get (25) and establish the soundness property of A′(and assuming (23), also the soundness of A). Let us now prove these three lemmas.

Proof of Lemma 4.10. To prove this lemma we need the following claim.

Claim 4.13. Let S ⊆ E be a symmetric subset, and let {t_{v}}_{v∈V} be real numbers. Then

e=(u,w)∈E [t_{u}t_{w} · 1_{S}(e)]≤ (\frac{|S|}{|E|})^{(p−2)/p} · [ _{v∼μ}|t_{v}|^{p}]^{2/p},  (31)

where 1_{S} denotes the indicator of the set S.

Proof. For every v ∈ V, let s(v) = \frac{|(\{v\}×V)∩S|}{d(v)} . Then by the definition of μ,

v∼μ [s(v)] = \frac{1}{|E|} · ∑_{v∈V}|(\{v\}× V) ∩ S| = \frac{|S|}{|E|}.  (32)

Now by Claim 4.6,

e=(u,w)∈E [t_{u}t_{w} · 1_{S}(e)] = \frac{1}{|E|} · ∑_{(u,w)∈S}t_{u}t_{w}

≤ \frac{1}{|E|} · ∑_{(u,w)∈S}|t_{u}|^{2}

= \frac{1}{|E|} · ∑_{v∈V}d(v) · s(v) · |t_{v}|^{2}
= _{v∼μ} [s(v) · |t_{v}|^{2}]
≤ [ _{v∼μ}s(v)^{p/(p−2)}]^{(p−2)/p} · [ _{v∼μ}|t_{v}|^{p}]^{2/p}
≤ [ _{v∼μ}s(v)]^{(p−2)/p} · [ _{v∼μ}|t_{v}|^{p}]^{2/p}
=^{(32)} (\frac{|S|}{|E|})^{(p−2)/p} · [ _{v∼μ}|t_{v}|^{p}]^{2/p},

and the proof of Claim 4.13 is complete.

We are now ready to bound (28). By our definition of S and by the Cauchy-Schwarz inequality we have that

(28) ≤ _{e=(u,w)∈E} [1_{S}(e) · ∥f_{u}∥_{2} · ∥f_{w}∥_{2}]
≤ (\frac{|S|}{|E|})^{(p−2)/p} · [ _{v∼μ}∥f_{v}∥_{2}^{p}]^{2/p}  (by Claim 4.13)
≤ ((a + b)^{2} · Opt(ℒ))^{(p−2)/p} · [ _{v∼μ}∥f_{v}∥_{p}^{p}]^{2/p}  (by (27))
≤ ((a + b)^{2} · Opt(ℒ))^{(p−2)/p},  (by (22))

as claimed.

Proof of Lemma 4.11. By the symmetry of E, the two terms in (29) are equal. Using the Cauchy-Schwarz inequality we thus have that

(29) = 2 _{e=(u,w)∈E} [ ∑_{\begin{matrix}i∈α(u) \\ π_{e}(i)∈γ(w) \end{matrix}} f̂_{u}(i)f̂_{w}(π_{e}(i))] ≤ 2 _{e=(u,w)∈E} [∥f_{u}∥_{2} · ( ∑_{\begin{matrix}i∈α(u) \\ π_{e}(i)∈γ(w) \end{matrix}} f̂_{w}(π_{e}(i))^{2})^{1/2}].  (33)

We now consider the sum inside the square-root in (33). From the definition of γ(w), we know that whenever π_{e}(i) ∈ γ(w),

f̂_{w}(π_{e}(i))^{2} ≤ \frac{∥f_{w}^{l}∥_{2}^{2}}{a + b} ≤ \frac{∥f_{w}∥_{2}^{2}}{a + b}

(this is because larger coefficients would have gone into α(w) or β(w)). Also, since |α(u)| = a, the number of summands in the sum in (33) is at most a, and so for every w,

( ∑_{\begin{matrix}i∈α(u) \\ π_{e}(i)∈γ(w) \end{matrix}} f̂_{w}(π_{e}(i))^{2})^{1/2} ≤ \sqrt{\frac{a}{a + b}} · ∥f_{w}∥_{2} ≤ \sqrt{\frac{a}{b}} · ∥f_{w}∥_{2}.  (34)

Substituting (34) in (33), we get

(29) ≤ 2 · \sqrt{\frac{a}{b}} · _{e=(u,w)∈E} [∥f_{u}∥_{2} · ∥f_{w}∥_{2}]
≤ 2 · \sqrt{\frac{a}{b}} · _{v∼μ} [∥f_{v}∥_{2}^{2}]  (using Claim 4.5)
≤ 2 · \sqrt{\frac{a}{b}} · ∥F∥_{2}^{2}  (using (22))
≤ 2 · \sqrt{\frac{a}{b}} = \frac{2ε}{γ_{p}^{2}}.  (by the definition of a and b)

This completes the proof of Lemma 4.11

Proof of Lemma 4.12. Using Cauchy-Schwarz and (22) we have that

(30) ≤ _{e=(u,w)∈E} [ ∑_{\begin{matrix}i∈β(u)∪γ(u) \\ π_{e}(i)∈β(w)∪γ(w) \end{matrix}} |f̂_{u}(i)||f̂_{w}(π_{e}(i))|]

≤ _{e=(u,w)∈E} [∥f_{u}^{β} + f_{u}^{γ}∥ _{2} · ∥f_{w}^{β} + f_{w}^{γ}∥ _{2}]≤ _{v∼μ} [∥f_{v}^{β} + f_{v}^{γ}∥ _{2}^{2}].  (35)

For every v ∈ V we would now like to bound ∥f_{v}^{β} + f_{v}^{γ}∥ _{2}^{2} by considering two cases. If

∥f_{v}^{β} + f_{v}^{γ}∥ _{2}^{2} ≥ \frac{1}{γ_{p}^{2}} · ∥f_{v}^{l}∥_{2}^{2}  (36)

then by the choice of the parameter a and the definition of β(v) and γ(v), we have that all of the squares of

the Fourier coefficients of f_{v}^{β} + f_{v}^{γ} are smaller than \frac{1}{a} · ∥f_{v}^{l}∥_{2}^{2} = \frac{ϕ(p,ε)}{γ_{p}^{2}} · ∥f_{v}^{l}∥_{2}^{2} ≤ ϕ(p, ε) · ∥f_{v}^{β} + f_{v}^{γ}∥ _{2}^{2}. So the definition of ϕ(p, ε), together with the fact that f_{v}^{α} is a symmetric random variable which is independent of the random variable f_{v}^{β} + f_{v}^{γ}, we deduce that

∥f_{v}^{l}∥_{p}^{2} = ∥f_{v}^{α} + f_{v}^{β} + f_{v}^{γ}∥ _{p}^{2} ≥ ∥f_{v}^{β} + f_{v}^{γ}∥ _{p}^{2} ≥ (1 − ε)γ_{p}^{2} · ∥f_{v}^{β} + f_{v}^{γ}∥ _{2}^{2}.  (37)

On the other hand, if (36) does not hold, then

∥f_{v}^{β} + f_{v}^{γ}∥ _{2}^{2} ≤ \frac{1}{γ_{p}^{2}} · ∥f_{v}^{l}∥_{p}^{2} ≤ \frac{1}{(1 − ε)γ_{p}^{2}} · ∥f_{v}^{l}∥_{p}^{2},  (38)

and thus (38) hold in both cases. Continuing (35), we therefore have that

(30) ≤ \frac{1}{(1 − ε)γ_{p}^{2}} · _{v∼μ} [∥f_{v}^{l}∥_{p}^{2}] ≤ \frac{1}{(1 − ε)γ_{p}^{2}} · [ _{v∼μ} ∥f_{v}^{l}∥_{p}^{p}]^{2/p} ≤ \frac{1 + 3/|V|}{(1 − ε)γ_{p}^{2}},

where in the last inequality we used Claim 4.9. This completes the proof of Lemma 4.12.

4.4 Removing diagonal entries

To complete the proof of the Theorem 4.2, it remain to define the actual form A, which will have no diagonal entries (that is, no non-multilinear terms), and to prove that it satisfies (23).

Identifying the source of diagonal entries. Let us begin by identifying the source of diagonal entries in A′. First, note that all the terms in A_{outer} are multilinear. This is true since it contains sums of terms of the form f̂_{u}(i_{1}) · f̂_{w}(i_{2}), where (u, w) ∈ E. Since by definition there are no loops in E, f̂_{u}(i_{1}) and f̂_{w}(i_{2}) are linear combinations of disjoint coordinates in F, and thus their product is multilinear in the coordinates of F.

As for A_{inner}, it is a weighted sum of terms of the form

A_{v}(F) = −B · ∑_{\begin{matrix}S⊆[r] \\ |S| 1 \end{matrix}} f̂_{v}(S)^{2},

where from the definition of f_{v} we have that

f̂_{v}(S)^{2} = ( _{j∈[D·d(v)]}[f̂_{v}^{j} (S)])^{2} = \frac{1}{D^{2} · d(v)^{2}}· ∑_{j_{1},j_{2}∈[D·d(v)]}f̂_{v}^{j_{1}} (S)f̂_{v}^{j_{2}} (S).

Here the only terms that may contribute diagonal entries are those for which j_{1} = j_{2}, which are of the form f̂_{v}^{j} (S)^{2}.

Defining A. Let us therefore define for every v ∈ V

A_{v}^{∗}(F) −B · ∑_{\begin{matrix}S⊆[r] \\ |S| 1 \end{matrix}} f̂_{v}(S)^{2} + \frac{B}{D^{2} · d(v)^{2}}· ∑_{j∈[D·d(v)]}∑_{\begin{matrix}S⊆[r] \\ |S| 1 \end{matrix}} f̂_{v}^{j} (S)^{2},

and set

A_{inner}^{∗}(F) _{v∼μ} [A_{v}^{∗}(F)]  and  A A_{inner}^{∗} + A_{outer}.

Now A does not have nonzero diagonal entries. Let us verify that it satisfies (23). For every F such that ∥F∥_{p} ≤ 1,

|A′(F) − A(F)|= |A_{inner}(F) − A_{inner}^{∗}(F)|

= _{v∼μ} [\frac{B}{D^{2} · d(v)^{2}}· ∑_{j∈[D·d(v)]}∑_{\begin{matrix}S⊆[r] \\ |S| 1 \end{matrix}} f̂_{v}^{j} (S)^{2}]

≤ \frac{B}{D} · _{v∼μ} _{j∈[D·d(v)]}[∑_{\begin{matrix}S⊆[r] \\ |S| 1 \end{matrix}} f̂_{v}^{j} (S)^{2} ]

(dropping a factor of 1/d(v) inside the expectation)

≤ \frac{B}{D} · _{v∼μ} _{j∈[D·d(v)]}∥f_{v}^{j} ∥_{2}^{2} ≤ \frac{B}{D} = \frac{1}{|V|},

where the last inequality follows from (21), and the last equality is from the choice of the parameters B and D. This gives (23), and concludes the proof of Theorem 4.2.

5 Discussion and open problems

Several open problems arise naturally from our work. We list some of them below.

• Both our algorithm, and our hardness result, do not yield anything non-trivial when 1 ≤ p < 2. It would be interesting to understand QM(p) in this case as well. When p = 1 it is easy to see that Opt_{1}(A) is up to a factor of 2 the same as max_{i,j∈[n]} |a_{ij}|. Thus there is a trivial factor 2 approximation algorithm for QM(1). We have recently learned from Elad Hazan and Nimrod Megiddo (personal communication) that they obtained a PTAS for QM(1).

• We did not try to prove an integrality gap lower bound for the convex program that we used in Section 3, though we believe that a matching integrality gap should follow from an adaptation of the method used in [3].

• Is γ_{p}^{2} the true hardness threshold for QM(p) for every fixed p > 2 (i.e. not only asymptotically as p → ∞)?

• It would be interesting to study the complexity of correlated quadratic programs on more general bodies K ⊆ ^{n}. Although our methods give non-trivial results in other cases, we did not pursue this research direction. In particular, if K = {x ∈ ^{n} : ∑ _{i=1}^{n} v(|x_{i}|) ≤ 1}, where v : _{+} → _{+} is convex (and computable), i.e. in the case of general one body potentials, a tempting conjecture would be that if v ( \sqrt{t}) is convex then the hardness threshold is ( v(g))^{2}, where g is a standard Gaussian random variable.

• Is it possible to remove the UGC assumption in Theorem 1.1? Is it possible to prove a standard NPhardness result in this context? Perhaps the complexity assumptions that appear in [5] can be used here as well.

• Is there a sharp hardness threshold in the Ising case (i.e. the L_{∞} problem in (1))? Currently the gap between the known upper and lower bounds in this case is large, and it would be interesting to get sharp results as in the case of finite p.

Acknowledgments

We thank Gérard Ben-Arous for helpful discussions on spin glasses.

References

[1] D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435:759–764, 2005.

[2] A. Alon and E. Berger. The Grothendieck constant of random and pseudo-random graphs. To appear in Discrete Optimization.

[3] N. Alon, K. Makarychev, Y. Makarychev, and A. Naor. Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006.

[4] N. Alon and A. Naor. Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput., 35(4):787–803 (electronic), 2006.

[5] S. Arora, E. Berger, G. Kindler, E. Hazan, and S. Safra. On non-approximability for quadratic programs. In 46th Annual Symposium on Foundations of Computer Science, pages 206–215. IEEE Computer Society, 2005.

[6] E. Artin. The gamma function. Translated by Michael Butler. Athena Series: Selected Topics in Mathematics. Holt, Rinehart and Winston, New York, 1964.

[7] C. P. Bachas. Computer-intractability of the frustration model of a spin glass. J. Phys. A: Math. Gen., 17:709–712, 1984.

[8] N. Bansal, S. Bravyi, and B. M. Terhal. A classical approximation scheme for the groundstate energy of Ising spin Hamiltonians on planar graphs. Preprint, 2007. Available at

http://arxiv.org/abs/0705.1115.

[9] F. Barahona. On the computational complexity of Ising spin glass models. J. Phys. A: Math. Gen., 15:3241–3253, 1981.

[10] M. Bellare and P. Rogaway. The complexity of approximating a nonlinear program. Math. Programming, 69(3, Ser. A):429–441, 1995.

[11] G. Ben Arous, A. Dembo, and A. Guionnet. Aging of spherical spin glasses. Probab. Theory Related Fields, 120(1):1–67, 2001.

[12] L. Bieche, R. Maynard, R. Rammal, and J. P. Uhry. On the ground states of the frustration model of a spin glass by a matching method of graph theory. J. Phys. A: Math. Gen., 13:2553–2576, 1980.

[13] A. Brieden. Geometric optimization problems likely not contained in . Discrete Comput. Geom., 28(2):201–209, 2002.

[14] M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for unique games (extended abstract). In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 205–214, New York, 2006. ACM.

[15] M. Charikar and A. Wirth. Maximizing quadratic programs: extending Grothendieck’s inequality. In 45th Annual Symposium on Foundations of Computer Science, pages 54–60. IEEE Computer Society, 2004.

[16] E. de Klerk, M. Laurent, and P. A. Parrilo. A PTAS for the minimization of polynomials of fixed degree over the simplex. Theoret. Comput. Sci., 361(2-3):210–225, 2006.

[17] U. Feige and L. Lovász. Two-prover one-round proof systems, their power and their problems. In STOC’92: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 733–744, New York, 1992. ACM.

[18] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.

[19] P. Hall. Rates of convergence in the central limit theorem, volume 62 of Research Notes in Mathematics. Pitman (Advanced Publishing Program), Boston, Mass., 1982.

[20] E. Halperin and E. Hazan. HAPLOFREQ—estimating haplotype frequencies efficiently. J. Comput. Biol., 13(2):481–500 (electronic), 2006.

[21] W. B. Johnson and J. Lindenstrauss. Basic concepts in the geometry of Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, pages 1–84. North-Holland, Amsterdam, 2001.

[22] S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 767–775 (electronic), New York, 2002. ACM.

[23] S. Khot and R. O’Donnell. SDP gaps and UGC-hardness for MAXCUTGAIN. In 47th Annual Symposium on Foundations of Computer Science, pages 217–226. IEEE Computer Society, 2006.

[24] J. Machta. The computational complexity of pattern formation. J. Stat. Phys., 70:949–966, 1993.

[25] A. Megretski. Relaxation of quadratic programs in operator theory and system analysis. Systems, Approximation, Singular Integral Operators, and Related Topics (Bordeaux, 2000), (3):365–392, 2001.

[26] A. Megretski. Relaxations of quadratic programs in operator theory and system analysis. In Systems, approximation, singular integral operators, and related topics (Bordeaux, 2000), volume 129 of Oper. Theory Adv. Appl., pages 365–392. Birkhäuser, Basel, 2001.

[27] A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic form over intersection of ellipsoids with common center. Math. Program., 86(3, Ser. A):463–473, 1999.

[28] A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic form over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463–473, 1999.

[29] Y. Nesterov. Global quadratic optimization via conic relaxation. Working paper CORE, 1998.

[30] H. Sompolinsky and A. Zippelius. Dynamic theory of the spin-glass phase. Phys. Rev. Lett., 47(5):359– 362, 1981.

[31] T.S.Motzkin and E. Straus. Maxima for graphs and a new proof of a theorem of turan. Canadian Journal of Mathematics, 17:533–540, 1965.

[32] P. van Beek. An application of Fourier methods to the problem of sharpening the Berry-Esseen inequality. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 23:187–196, 1972.

[33] S. Wolfram. Undecidability and intractability in theoretical physics. Phys. Rev. Lett., 54:735–738, 1985.