Linear equations modulo 2 and the L_{1} diameter of convex bodies

Subhash Khot^{∗} Georgia Institute of Technology

     khot@cc.gatech.edu

Assaf Naor^{†} Courant Institute of Mathematical Sciences

                                       naor@cims.nyu.edu

Abstract

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {a_{ijk}}_{i,j,k=1}^{n} such that for all i, j, k ∈ {1, …, n} we have a_{ijk} = a_{ikj} = a_{kji} = a_{jik} = a_{kij} = a_{jki} and a_{iik} = a_{ijj} = a_{iji} = 0, computes a number Alg(A) which satisfies with probability at least \frac{1}{2},

Ω (\sqrt{\frac{logn}{n}})· max_{x∈\{−1,1\}^{n}} ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} ≤ Alg(A) ≤ max_{x∈\{−1,1\}^{n}} ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k}.

On the other hand, we show via a simple reduction from a result of H�stad and Venkatesh [22] that under the assumption NP DTIME (n^{(logn)^{O(1)}}), for every ε > 0 there is no algorithm that approximates max_{x∈{−1,1}^{n}}∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} within a factor of 2^{(logn)^{1−ε}} in time 2^{(logn)^{O(1)}}.

Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in ^{n} with respect to the L_{1} norm. We show that it is possible to do so up to a multiplicative error of O ( \sqrt{\frac{n}{logn}}), while no randomized polynomial time algorithm can achieve accuracy o ( \sqrt{\frac{n}{logn}}). This resolves a question posed by Brieden, Gritzmann, Kannan, Klee, Lovász and Simonovits in [10].

We apply our new algorithm to improve the algorithm of H�stad and Venkatesh [22] for the Max-E3-Lin-2 problem. Given an over-determined system E of N linear equations modulo 2 in n ≤ N Boolean variables, such that in each equation appear only three distinct variables, the goal is to approximate in polynomial time the maximum number of satisfiable equations in E minus \frac{N}{2} (i.e. we subtract the expected number of satisfied equations in a random assignment). H�stad and Venkatesh [22] obtained an algorithm which approximates this value up to a factor of O ( \sqrt{N}). We obtain a O ( \sqrt{\frac{n}{logn}})approximation algorithm. By relating this problem to the refutation problem for random 3 − CNF formulas we give evidence that obtaining a significant improvement over this approximation factor is likely to be difficult.

∗Research supported in part by NSF CARREER award CCF-0643626, and a Microsoft New Faculty Fellowship.

†Research supported by NSF grants CCF-0635078 and DMS-0528387.

1 Introduction

A function f : {−1, 1}^{n} → has Fourier expansion f (x) = ∑ _{S⊆{1,...,n}}f̂(S) ∏ _{i∈S} x_{i}. Assume that f has a succinct representation in phase space, i.e. only polynomially many of the Fourier coefficients f̂(S) are non-zero. Can we then compute in polynomial time a good approximation of the maximum of f over the discrete cube {−1, 1}^{n}? In other words, if we are given polynomially many Fourier coefficients, is there a way to approximate max_{x∈{−1,1}^{n}}f (x) while only looking at the values of f on a tiny part of the cube? As we shall see below, under widely believed complexity assumptions the answer to this question is generally negative. But, under some additional structural information on the support of he Fourier transform it is possible to achieve this goal, and when this occurs such phenomena have powerful algorithmic applications. Currently our understanding of this fundamental problem is far from satisfactory, and the purpose of the present paper is to investigate cases which have previously eluded researchers. As a result, we uncover new connections to problems in algorithmic convex geometry and combinatorial optimization.

The Fourier maximization problem described above has been investigated extensively in the quadratic case, partly due to its connections to various graph partitioning problems. In [3] it has been shown that a classical inequality of Grothendieck can be used to give a constant factor approximation algorithm for computing the maximum of functions f : {−1, 1}^{n} × {−1, 1}^{m} → which have the form f (x, y) = ∑ _{i=1}^{n} ∑ _{j=1}^{m} a_{ij}x_{i}y_{j}. This algorithm has various applications, including algorithmic versions of Szemerédi’s regularity lemma. In the non-bipartite case several researchers [27, 25, 12] have discovered an algorithm which computes up to a factor O(logn) the maximum of functions f : {−1, 1}^{n} → which have the form f (x) = ∑ _{i,j=1}^{n} a_{ij}x_{i}x_{j}, where the matrix (a_{ij}) is assumed to be symmetric and vanish on the diagonal. This result was shown in [12] to imply the best-known approximation algorithms to graph partitioning problems such as MAXCUTGAIN and Correlation Clustering. In [2] the structure of the “Fourier support graph”, i.e. the pairs {i, j} ∈ {1, …, n} for which a_{ij} 0, was taken into account. It was shown there that there exists an approximation algorithm which approximates the maximum of f up to a factor O(logϑ) = O(logχ), where ϑ is the Lovász Theta Function of the complement of the Fourier support graph, and χ is the chromatic number of this graph. We refer to [2] for more information on this topic, as well as its connection to the evaluation of ground states of spin glasses.

Negative results on the performance of the above mentioned algorithms, as well as complexity lower bounds were obtained in [3, 2, 5, 24, 1]. In particular, in was shown in [2] that the semidefinite relaxation that was used in the O(logn) algorithm discussed above had integrality gap Ω(logn). Moreover in [5] it was shown that unless NP ⊆ DTIME (n^{O((logn)^{3})})there is no polynomial time algorithm which approximates the maximum of ∑ _{i,j=1}^{n} a_{ij}x_{i}x_{j} on {−1, 1}^{n} up to a factor smaller that (logn)^{γ}, where γ is a universal constant. It was also shown in [5] that under the assumption of the existence of sufficiently strong PCPs it is also NP-hard to approximate this problem to within a factor of O(logn).

The motivation for the present paper is to study the case of functions whose Fourier expansion is supported on the third level. Specifically, given a 3-tensor of real numbers A = {a_{ijk}}_{i,j,k=1}^{n} such that for all i, j, k ∈ {1, …, n} we have a_{ijk} = a_{ikj} = a_{kji} = a_{jik} = a_{kij} = a_{jki} and a_{iik} = a_{ijj} = a_{iji} = 0, we wish to approximate the maximum of the function f : {−1, 1}^{n} → given by f (x) = ∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k}. Despite being a modest goal, this problem has eluded researchers for some time, as the “obvious” semidefinite programming approach that was previously applied to the quadratic case does not generalize to the degree-3 case. As we shall see below, this issue reflects a major difference from the quadratic case: Unless NP ⊆ DTIME (n^{(logn)^{O(1)}}), for every ε > 0 there is no algorithm that approximates the maximum of f within a factor of 2^{(logn)^{1−ε}} in time 2^{(logn)^{O(1)}}. On the other hand, we will derive here a polynomial time algorithm which approximates the maximum of f to within a factor of O ( \sqrt{\frac{n}{logn}}). This algorithm is based on a novel connection between this problem and the problem of efficient computation of the diameter of convex bodies under the ℓ_{1}^{n} norm, which is the main new insight of the present paper. We shall now describe our new approach, and its application to a fundamental problem in combinatorial optimization: The Max-E3-Lin-2 problem.

We associate to every 3-tensor A as above a convex body K_{A} ⊆ ^{n}. The body K_{A} admits a polynomial time solution to the weak optimization problem for linear functionals (see [19, 18] for the relevant background on convex optimization). Moreover, we show that the ℓ_{1}^{n} diameter of K_{A}, i.e. diam_{1}(K_{A}) max_{a,b∈K_{A}}∥a − b∥_{1}, is within a constant factor of max_{x_{i}∈{−1,1}}∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k}. This step is crucially based on an application of Grothendieck’s inequality. We therefore reduce the level-3 Fourier maximization problem to the following question: Given a convex body K ⊆ ^{n} with a weak optimization oracle, approximate in oracle-polynomial time its ℓ_{1}^{n} diameter diam_{1}(K).

Such problems have been studied extensively in the literature, though mostly in the context of the Euclidean ℓ_{2}^{n} diameter (see for example [6, 8, 18, 10, 9, 31] and the references therein). In particular, a famous result of Bárány and Füredi states that no deterministic polynomial time algorithm can approximate the ℓ_{2}^{n}

diameter of convex bodies up to a factor of o ( \sqrt{\frac{n}{logn}}). In the paper [10] of Brieden, Gritzmann, Kannan, Klee, Lovász and Simonovits it is shown that unlike the case of volume computation, randomization does not help when it comes to approximating the Euclidean diameter of convex bodies: The same lower bound holds also for the accuracy of randomized oracle-polynomial time algorithms. The paper [10] also studies the case of the ℓ_{1}^{n} diameter, or more generally the ℓ_{p}^{n} diameter, i.e. diam_{p}(K) max_{a,b∈K_{A}}∥a − b∥_{p}. It is shown there that there is an oracle polynomial time algorithm which approximates diam_{1}(K) to within a factor of O ( \sqrt{n}), and no polynomial time algorithm can achieve accuracy better than O (^{\frac{\sqrt{n}}{logn}}). When 1 < p ≤ 2

it is shown in [10] that diam_{p}(K) can be approximated within a factor O (\frac{\sqrt{n}}{(logn)^{(p−1)/p}}), and no polynomial

time algorithm can achieve accuracy better than O_{p} ( \sqrt{\frac{n}{logn}}). These bounds coincide only when p = 2, and the question of closing the gap in the remaining cases was raised in [10] (see also [9]). Here we resolve this problem by showing that the accuracy threshold for randomized oracle-polynomial algorithms that compute diam_{p}(K) is Θ ( \sqrt{\frac{n}{logn}})for all 1 ≤ p ≤ 2. Our improved accuracy lower bound when p = 1 is a slight variant of the argument in [10]. The main issue is obtaining an improved approximation algorithm—our approach is different from the polyhedral approximation of the ℓ_{p}^{n} ball that was used in [10] (though we believe that the construction of [10] is of independent interest).

We apply the results described above to obtain a significant improvement to the Max-E3-Lin-2 algorithm of H�stad and Venkatesh [22]. This fundamental problem is described as follows. Consider a system E of N linear equations modulo 2 in n Boolean variables z_{1}, …, z_{n}, such that in each equation appear only three distinct variables. We assume throughout that N ≥ n (thus avoiding degenerate cases). Let MAXSAT(E) be the maximum number of equations in E that can be satisfied simultaneously. A random assignment of these variables satisfies in expectation \frac{N}{2} equations, so in the Max-E3-Lin-2 problem it is natural to ask for an approximation algorithm to MAXSAT(E) − \frac{N}{2}. This problem was studied extensively by H�stad and Venkatesh in [22], where the best known upper and lower bounds were obtained. In particular, using the powerful methods of H�stad [21] they show that unless NP ⊆ DTIME (n^{(logn)^{O(1)}}), for every ε > 0 there is no algorithm that approximates MAXSAT(E) − \frac{N}{2} within a factor of 2^{(logn)^{1−ε}} in time 2^{(logn)^{O(1)}}. Moreover, they design a randomized polynomial time algorithm which approximates MAXSAT(E) − \frac{N}{2} to within a factor of O ( \sqrt{N}).

Let E be a system of linear equations as above. Write a_{ijk}(E) = 1 if the equation z_{i} + z_{j} + z_{k} = 0 is in the system E. Similarly write a_{ijk}(E) = −1 if the equation z_{i} + z_{j} + z_{k} = 1 is in E. Finally, write a_{ijk}(E) = 0 if no equation in E corresponds to z_{i} + z_{j} + z_{k}. Assume that the assignment (z_{1}, …, z_{k}) satisfies m of the equations in E. Then ∑ _{i,j,k=1}^{n} a_{ijk}(E)(−1)^{z_{i}+z_{j}+z_{k}} = m − (N − m) = 2 (m − \frac{N}{2}). It follows that

max_{x_{i}∈\{−1,1\}} ∑_{i,j,k=1}^{n} a_{ijk}(E)x_{i}x_{j}x_{k} = max_{z_{i}∈\{0,1\}} ∑_{i,j,k=1}^{n} a_{ijk}(E)(−1)^{z_{i}+z_{j}+z_{k}} = 2 (MAXSAT(E) − \frac{N}{2}) .

Thus our algorithm yields a O ( \sqrt{\frac{n}{logn}}) approximation to the Max-E3-Lin-2 problem. Note that when N = Θ(n) our improvement over the H�stad-Venkatesh algorithm is only logarithmic, but typically N can be as large as Θ (N^{3}). The above reasoning also allows us to apply the H�stad-Venkatesh hardness result for Max-E3-Lin-2 that was described above to the level-3 Fourier maximization problem. In particular it follows that this problem is computationally much harder than the quadratic case, in which a O(logn) approximation is possible. Finally, our reasoning comes full circle to shed light on the problem of approximating the ℓ_{1}^{n} diameter diam_{1}(K). While the proof in [10] is essentially an “entropy argument” showing that there are simply too many convex bodies to allow an approximation factor better than O ( \sqrt{n}), our reduction produces a concrete family of convex bodies for which computing the ℓ_{1}^{n} diameter within a factor of is 2^{(logn)^{1−ε}} is hard.

2 A new algorithm for Max-E3-Lin-2

As described in the reduction that was presented in the introduction, our new algorithm for Max-E3-Lin-2 will follow from the more general algorithm for approximating the maximum of functions whose Fourier transform is supported on subsets of size 3. So, from now on let {a_{ijk}}_{i,j,k=1}^{n} be real numbers such that for all i, j, k ∈ {1, …, n} we have a_{ijk} = a_{ikj} = a_{kji} = a_{jik} = a_{kij} = a_{jki} and a_{iik} = a_{ijj} = a_{iji} = 0. Our first lemma reduces the problem of maximizing ∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} to the analogous tripartite case. Note that such a result is false in the quadratic case. Indeed, Theorem 3.5 in [2] implies that the gap between max_{x_{i}∈\{−1,1\}}∑ _{i,j=1}^{n} a_{ij}x_{i}x_{j} and max_{x_{i},y_{j}∈\{−1,1\}}∑ _{i,j=1}^{n} a_{ij}x_{i}y_{j} can be as large as Ω (\frac{n}{logn}). The key “trick” which allows us to prove that this cannot happen in the level-3 case is identity (1) below.

Lemma 2.1. The following inequalities hold true:

\frac{1}{10} max_{x_{i},y_{j},z_{k}∈\{−1,1\}}∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}z_{k} ≤ max_{x_{i}∈\{−1,1\}} ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} ≤ max_{x_{i},y_{j},z_{k}∈\{−1,1\}}∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}z_{k}.

Proof. Define

M = max_{x_{i},y_{j},z_{k}∈{−1,1}}∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}z_{k},

and

m = max_{x_{i}∈{−1,1}} ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k}.

Clearly m ≤ M, so we need to show that that M ≤ 10m. To see this observe first of all that ∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} is linear in x_{i} for each i. This implies that

m = max_{|x_{i}|≤1} ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k}.

Moreover, since ∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} changes sign if we replace x_{i} by −x_{i} for each i, we see that

m = max_{|x_{i}|≤1} | ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k}|.

Now, for each i, j, k ∈ {1, …, n} we have the identity

2x_{i}y_{j}y_{k} + 2x_{j}y_{i}y_{k} + 2x_{k}y_{i}y_{j} = (x_{i} + y_{i})(x_{j} + y_{j})(x_{k} + y_{k}) + (x_{i} − y_{i})(x_{j} − y_{j})(x_{k} − y_{k}) − 2x_{i}x_{j}x_{k} − 2y_{i}y_{j}y_{k}. (1)

Multiplying this identity by a_{ijk}, summing over all i, j, k ∈ {1, …, n}, and using the symmetries of the coefficients a_{ijk}, we see that

6 ∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}y_{k} = 8 ∑_{i,j,k=1}^{n} a_{ijk} \frac{x_{i} + y_{i}}{2} · \frac{x_{j} + y_{j}}{2} · \frac{x_{k} + y_{k}}{2} + 8 ∑_{i,j,k=1}^{n} a_{ijk} \frac{x_{i} − y_{i}}{2} · \frac{x_{j} − y_{j}}{2} · \frac{x_{k} − y_{k}}{2}

− 2 ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} − 2 ∑_{i,j,k=1}^{n} a_{ijk}y_{i}y_{j}y_{k}.

It follows that

M′ max_{x_{i},y_{j}∈\{−1,1\}}| ∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}y_{k}|≤ \frac{20}{6}m = \frac{10}{3}m.

As before, because ∑ _{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}y_{k} is linear in each of the variables x_{i} and y_{j}, we have the identity

M′ = max_{|x_{i}|,|y_{j}|≤1}| ∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}y_{k}|.

Now, consider the identity

y_{j}z_{k} + y_{k}z_{j} = (y_{j} + z_{j})(y_{k} + z_{k}) − y_{j}y_{k} − z_{j}z_{k}.

Multiplying by a_{ijk}x_{i}, and summing up, we get the identity

2 ∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}z_{k} = 4 ∑_{i,j,k=1}^{n} a_{ijk}x_{i} · \frac{y_{j} + z_{j}}{2} · \frac{y_{k} + z_{k}}{2} − ∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}y_{k} − ∑_{i,j,k=1}^{n} a_{ijk}x_{i}z_{j}z_{k} ≤ 6M′ ≤ 20m.

It follows that M ≤ 10m, as required.

Let (ℓ_{2}^{n})_{∞}^{n} denote the space of v⃗= (v_{1}, …, v_{n}) ∈ ( ^{n})^{n}, equipped with the norm

∥v⃗∥_{(ℓ_{2}^{n})_{∞}^{n}} max_{1≤j≤n} ∥v_{j}∥_{2}.

Similarly we let (ℓ_{2}^{n})_{1}^{n} denote the space of v⃗= (v_{1}, …, v_{n}) ∈ ( ^{n})^{n}, equipped with the norm

∥v⃗∥_{(ℓ_{2}^{n})_{1}^{n}} ∑_{j=1}^{n} ∥v_{j}∥_{2}.

Any n × n matrix B = (b_{ij}) ∈ M_{n}( ) can be tensorized with the identity to yield an operator B ⊗ I : (ℓ_{2}^{n})_{∞}^{n} → (ℓ_{2}^{n})_{1}^{n} given by

((B ⊗ I)v⃗)_{i} ∑_{j=1}^{n} b_{ij}v_{j}.

The operator norm of B ⊗ I is given by

∥B ⊗ I∥_{(ℓ_{2}^{n})_{∞}^{n} →(ℓ_{2}^{n})_{1}^{n}} = max {∑_{i=1}^{n} ∥∑_{j=1}^{n} b_{ij}v_{j} ∥_{2} : max_{1≤j≤n} ∥v_{j}∥_{2} ≤ 1}

= max {∑_{i=1}^{n} ⟨∑_{j=1}^{n} b_{ij}v_{j}, u_{i}⟩: max_{1≤j≤n} ∥v_{j}∥_{2} ≤ 1 ∧ max_{1≤i≤n} ∥u_{i}∥_{2} ≤ 1}

= max_{∥u_{i}∥_{2},∥v_{j}∥_{2}≤1}∑_{i,j=1}^{n} b_{ij} ⟨u_{i}, v_{j}⟩.  (2)

By Lemma 2.1 our goal is to approximate the value

Opt(A) max_{x_{i},y_{j},z_{k}∈{−1,1}}∑_{i,j,k=1}^{n} a_{ijk}x_{i}y_{j}z_{k}.

For every x ∈ {−1, 1}^{n} define an n × n matrix A(x) ∈ M_{n}( ) by

A(x)_{jk} = ∑_{i=1}^{n} a_{ijk}x_{i}.

Since for each x ∈ ^{n} we have ∥A(x) ⊗ I∥_{(ℓ_{2}^{n})_{∞}^{n} →(ℓ_{2}^{n})_{1}^{n}} ≥ max_{|y_{j}|,|z_{k}|≤1}∑ _{j,k=1}^{n} A(x)_{ij}y_{j}z_{k} it follows that Opt(A) ≤ max_{x∈{−1,1}^{n}}∥A(x) ⊗ I∥_{(ℓ_{2}^{n})_{∞}^{n} →(ℓ_{2}^{n})_{1}^{n}} . On the other hand, using (2), Grothendieck’s inequality (see the discussion in [3]) says that

max_{x∈{−1,1}^{n}}∥A(x) ⊗ I∥_{(ℓ_{2}^{n})_{∞}^{n} →(ℓ_{2}^{n})_{1}^{n}} ≤ max_{x∈{−1,1}^{n}}K_{G} max_{y,x∈{−1,1}^{n}}∑_{j,k=1}^{n} A(x)_{jk}y_{j}z_{k} = K_{G} · Opt(A),

where K_{G} ≤ 2 is Grothendieck’s constant. It therefore suffices to approximate the value of

max_{x∈{−1,1}^{n}}∥A(x) ⊗ I∥_{(ℓ_{2}^{n})_{∞}^{n} →(ℓ_{2}^{n})_{1}^{n}} .

Define a norm ∥ · ∥_{A} on ^{n} by ∥x∥_{A} ∥A(x) ⊗ I∥_{(ℓ_{2}^{n})_{∞}^{n} →(ℓ_{2}^{n})_{1}^{n}} . Then the unit ball B_{A} {x ∈ ^{n} : ∥x∥_{A} ≤ 1} is a centrally symmetric convex body. Denote by K_{A} = B_{A}^{∘} the polar of B_{A}, i.e.

K_{A} = {y ∈ ^{n} : ∀x ∈ B_{A}, ⟨x, y⟩ ≤ 1}.

Then

max_{x∈\{−1,1\}^{n}}∥A(x) ⊗ I∥_{(ℓ_{2}^{n})_{∞}^{n} →(ℓ_{2}^{n})_{1}^{n}} = max_{∥x∥_{∞} ≤1}∥x∥_{A} = max_{∥x∥_{∞} ≤1} max_{y∈K_{A}}⟨x, y⟩ = max_{y∈K_{A}} max_{∥x∥_{∞} ≤1}⟨x, y⟩ = max_{y∈K_{A}}∥y∥_{1} = \frac{1}{2} diam_{1} (K_{A}).

We have thus reduced our original problem to approximating diam_{1} (K_{A}) in polynomial time. Note that (2) implies that the computation of ∥x∥_{A}is a semidefinite program. Therefore by the theory of Grötschel, Lovász and Schrijver [19] it follows that linear functionals can be optimized on B_{A} in polynomial time. As shown in [19], this property is preserved under polarity, i.e. linear functionals can be optimized on B_{A}^{∘} = K_{A} in polynomial time. We have therefore reduced the problem of approximating max_{x_{i}∈{−1,1}}∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} to the problem of approximating diam_{1}(K) in oracle polynomial time, where K is a centrally symmetric convex body with a weak optimization oracle. This problem is resolved in Section 3, thus proving the following theorem, which is our main result.

Theorem 2.2. There is a randomized polynomial time algorithm which, given a 3-tensor A = {a_{ijk}}_{i,j,k=1}^{n} such that for all i, j, k ∈ {1, …, n} we have a_{ijk} = a_{ikj} = a_{kji} = a_{jik} = a_{kij} = a_{jki} and a_{iik} = a_{ijj} = a_{iji} = 0, computes a number Alg(A) which satisfies with probability at least \frac{1}{2},

max_{x∈\{−1,1\}^{n}} ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} ≤ Alg(A) ≤ O ( \sqrt{\frac{n}{logn}}) max_{x∈\{−1,1\}^{n}} ∑_{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k}.

3 An approximation algorithm for the L_{1} diameter

The main result of this section is the following theorem, which settles a problem posed by Brieden, Gritzmann, Kannan, Klee, Lovász and Simonovits in [10].

Theorem 3.1. Let K ⊆ ^{n} be a convex body with a weak optimization oracle. Then there exists a randomized algorithm which computes in oracle-polynomial time a number Alg(K) such that with probability at least \frac{1}{2},

\frac{1}{2} \sqrt{\frac{logn}{n}} · diam_{1}(K) ≤ Alg(K) ≤ diam_{1}(K).

On the other hand, no randomized oracle-polynomial time algorithm can compute diam_{1}(K) with accuracy o ( \sqrt{\frac{n}{logn}}).

Since we will be only using Theorem 3.1 when K is 0-symmetric, i.e. K = −K, we will prove it under this assumption. This is only for the sake of simplifying the notation—identical arguments work in the general case. Our starting point is the following distributional inequality.

Lemma 3.2. For every δ ∈ (0, \frac{1}{2}) there is a constant c(δ) > 0 with the following property. Fix a = (a_{1}, …, a_{n}) ∈ ^{n} and let ε_{1}, …, ε_{n} be i.i.d. symmetric Bernoulli random variables. Then

Pr (∑_{j=1}^{n} a_{j}ε_{j} ≥ \sqrt{\frac{δ logn}{n}} · ∥a∥_{1})≥ \frac{c(δ)}{n^{δ}}.

Proof. Write X = ∑ _{j=1}^{n} a_{j}ε_{j}. Assume first of all that

\frac{4∥a∥_{2}^{2} \sqrt{n}}{∥a∥_{1}^{2}}> \frac{1}{12n^{δ}}.  (3)

The classical Paley-Zygmund inequality [28, 23, 4] states that for every θ ∈ (0, 1) we have

Pr(X^{2} ≥ θ X^{2}) ≥ (1 − θ)^{2} · \frac{( X^{2})^{2}}{X^{4}} ≥ \frac{(1 − θ)^{2}}{9} ,  (4)

where we used the well known (and easy) fact that X^{4} ≤ 9 ( X^{2})^{2}.

The inclusion of events \{X^{2} ≥ θ\}⊆ \{X ≥ \sqrt{θ}\}∪ \{−X ≥ \sqrt{θ}\}, and the fact that X is symmetric, implies that Pr(X ≥ \sqrt{θ}) ≥ \frac{1}{2} Pr(X^{2} ≥ θ). Since δ < \frac{1}{2} there is n_{0}(δ) ∈ such that for every n ≥ n_{0}(δ) we have \frac{48δ logn}{n^{\frac{1}{2}−δ}} < \frac{1}{2}. For such n we deduce that

Pr (∑_{j=1}^{n} a_{j}ε_{j} ≥ \sqrt{\frac{δ logn}{n}} · ∥a∥_{1})≥ \frac{1}{2} Pr(X^{2} ≥ \frac{δ logn}{n}∥a∥_{1}^{2}) ≥^{(3)} \frac{1}{2} Pr(X^{2} ≥ \frac{48δ logn}{n^{\frac{1}{2}−δ}} · X^{2})≥^{(4)} \frac{1}{72}.

Hence Lemma 3.2 holds assuming (3) and n ≥ n_{0}(δ). By adjusting c(δ) the required result holds also when n ≤ n_{0}(δ), so it remains to deal with the case

\frac{4∥a∥_{2}^{2} \sqrt{n}}{∥a∥_{1}^{2}}≤ \frac{1}{12n^{δ}}.  (5)

Assuming (5) we define S \{j ∈ \{1, …, n\} : |a_{j}| < \frac{2∥a∥_{2}^{2}}{∥a∥_{1}}\}. Then

∥a∥_{1} = ∑_{j S} |a_{j}| + ∑_{j∈S} |a_{j}| ≤ \frac{∥a∥_{1}}{2∥a∥_{2}^{2}} ∑_{j S} a_{j}^{2} + \sqrt{|S| ∑_{j∈S} a_{j}^{2}} ≤ \frac{∥a∥_{1}}{2}+ \sqrt{n ∑_{j∈S} a_{j}^{2}}.

Hence,

\sqrt{∑_{j∈S} a_{j}^{2}} ≥ \frac{∥a∥_{1}}{2 \sqrt{n}}.  (6)

Write Y = ∑ _{j∈S} a_{j}ε_{j} and Z = X − Y. For every t ∈ we have {Y ≥ 2t} ⊆ {Y + Z ≥ t} ∪ {Y − Z ≥ t}. Since Y + Z and Y − Z have the same distribution as X, it follows that Pr(X ≥ t) ≥ \frac{1}{2} Pr(Y ≥ 2t). Let g be a standard Gaussian random variable. By the Berry-Esseen inequality (see [20]. The constant we use below follows from [30]) we know that

Pr(Y ≥ 2t) = Pr( \frac{Y}{\sqrt{Y^{2}}} ≥ \frac{2t}{\sqrt{Y^{2}}}) ≥ Pr( \frac{Y}{\sqrt{Y^{2}}} ≥ \frac{t \sqrt{n}}{∥a∥_{1}}) ≥ Pr(g ≥ \frac{t \sqrt{n}}{∥a∥_{1}}) − max_{j∈S} \frac{|a_{j}|}{\sqrt{∑ _{k∈S} a_{k}^{2}}}

≥^{(6)} \frac{1}{\sqrt{2π}} exp (−\frac{t^{2}n}{∥a∥_{1}^{2}}) − \frac{4∥a∥_{2}^{2} \sqrt{n}}{∥a∥_{1}^{2}}.

Plugging t = \sqrt{\frac{δ logn}{n}} · ∥a∥_{1} we get that

Pr (∑_{j=1}^{n} a_{j}ε_{j} ≥ \sqrt{\frac{δ logn}{n}} · ∥a∥_{1})≥ \frac{1}{2} Pr(Y ≥ 2t) ≥ \frac{1}{6n^{δ}} − \frac{4∥a∥_{2}^{2} \sqrt{n}}{∥a∥_{1}^{2}} ≥^{(5)} \frac{1}{12n^{δ}},

as required.

Proof of Theorem 3.1. Let {ε_{ij} : i ∈ {1, …, m}, j ∈ {1, …, n}} be i.i.d. symmetric Bernoulli random variables. Compute the number

Alg(K) 2 max_{1≤i≤m} max_{a∈K} ∑_{j=1}^{n} a_{j}ε_{ij}.

Then Alg(K) ≤ 2 max_{a∈K} ∥a∥_{1} = diam_{1}(K). Moreover, M can be computed using O(m) oracle calls. Now, fix a ∈ K such that ∥a∥_{1} = \frac{1}{2} diam_{1}(K). Using Lemma 3.2 we see that there exists a universal constant c > 0 for which

Pr (Alg(K) > \frac{1}{2} \sqrt{\frac{logn}{n}} · diam_{1}(K))= 1 − Pr (⋂_{i=1}^{m} \{∑_{j=1}^{n} a_{j}ε_{ij} < \frac{1}{2} \sqrt{\frac{logn}{n}} · ∥a∥_{1}\})

≥ 1 − (1 − \frac{c}{\sqrt[4]{n}})^{m} ≥ 1 − exp(− \frac{cm}{\sqrt[4]{n}}) .

Choosing m = ⌈^{\frac{\sqrt[4]{n}}{c}}⌉we see that with probability at least \frac{1}{2},

\frac{1}{2} \sqrt{\frac{logn}{n}} · diam_{1}(K) ≤ Alg(K) ≤ diam_{1}(K),

as required.

The algorithmic lower bound in Theorem 3.1is essentially already contained in [10]—the authors simply overlooked there an easy stronger upper bound on the volume of polytopes inscribed in in the cube [−1, 1]^{n}. In Proposition 1.10 in [10] the authors prove that for every 0-symmetric polytope P ⊆ [−1, 1]^{n} with at most 2k vertices, where 20 log_{2} (\frac{k}{n} + 1) ≤ n ≤ k,

(vol(P))^{1/n} ≤ O(1) \sqrt{1 + logn} · \sqrt{\frac{log(\frac{k}{n} + 1)}{n}} .  (7)

The term \sqrt{1 + logn} in (7) is precisely the reason why the lower bound in [10] for the accuracy of random-

ized algorithms which compute diam_{1}(K) was Ω (^{\frac{\sqrt{n}}{logn}}) instead of O ( \sqrt{\frac{n}{logn}}). This term can be removed as follows.

Let B_{2}^{n} be the standard unit Euclidean ball of ℓ_{2}^{n}. Write P = conv{±v_{1}, …, ±v_{k}}, where v_{i} ∈ [−1, 1]^{n}. Then \frac{v_{i}}{\sqrt{n}} ∈ B_{2}^{n}, and by the results of [6, 11, 17] we deduce that

(\begin{matrix}vol & ( \frac{1}{\sqrt{n}}P) \\ vol & (B_{2}^{n}) \end{matrix})^{1/n} ≤ O(1) \sqrt{\frac{log(\frac{k}{n} + 1)}{n}} .

Since (vol(B_{2}^{n}))^{1/n} = Θ ( \frac{1}{\sqrt{n}}) it follows that

(vol(P))^{1/n} ≤ O(1) \sqrt{\frac{log(\frac{k}{n} + 1)}{n}} .

3.1 The case of the L_{p} diameter, 1 < p < 2

Fix p ∈ (1, 2), and define q = \frac{p}{p−1} > 2. Let h_{1}, …, h_{n} be i.i.d. random variables whose density is \frac{q}{2Γ(1/q)}e^{−|t|^{q}}. Let H be the random vector (h_{1}, …, h_{n}) ∈ ^{n}. Then the random variables H/∥H∥_{q} and ∥H∥_{q} are independent [29] (see [7] for more information on this phenomenon). The following lemma is analogous to Lemma 3.2.

Lemma 3.3. There exist universal constants δ, c_{1}, c_{2} > 0 such that for every a = (a_{1}, …, a_{n}) ∈ ^{n} we have

Pr (⟨\frac{H}{∥H∥_{q}}, a⟩≥ \sqrt{\frac{δ logn}{n}} · ∥a∥_{p})≥ \frac{c_{1}}{n^{c_{2}}}.

Proof. The random variable ∥H∥_{q} has density \frac{q}{Γ(n/q)}u^{n−1}e^{−u^{q}} for u > 0 (see for example [26]). Hence for every t ∈ (0, 1) we have

e^{t∥H∥_{q}^{q}}= \frac{q}{Γ(n/q)}∫ _{0}^{∞} e^{tu^{q}}· u^{n−1}e^{−u^{q}}du = \frac{q}{Γ(n/q)}∫ _{0}^{∞} u^{n−1}e^{−[(1−t)^{1/q}u]^{q}}du = \frac{1}{(1 − t)^{n/q}}.

Since q ≥ 2 it follows that

Pr(∥H∥_{q} ≥ n^{1/q})≤ e^{−n(1− \frac{1}{e})} e^{(1− \frac{1}{e})∥H∥_{q}^{q}} = e^{−n(1− \frac{1}{e}− \frac{1}{q})} ≤ e^{−n(\frac{1}{2}− \frac{1}{e})} ≤ e^{−n/8}.  (8)

Using the independence of H/∥H∥_{q} and ∥H∥_{q} we deduce that

Pr (⟨\frac{H}{∥H∥_{q}}, a⟩≥ \sqrt{\frac{δ logn}{n}} · ∥a∥_{p}) ≥ Pr (⟨\frac{H}{∥H∥_{q}}, a⟩≥ \sqrt{\frac{δ logn}{n}} · ∥a∥_{p})Pr(∥H∥_{q} ≤ n^{1/q})

= Pr (⟨\frac{H}{∥H∥_{q}}, a⟩≥ \sqrt{\frac{δ logn}{n}} · ∥a∥_{p} ∧ ∥H∥_{q} ≤ n^{1/q})

≥ Pr (⟨H, a⟩≥ n^{1/q} \sqrt{\frac{δ logn}{n}} · ∥a∥_{p} ∧ ∥H∥_{q} ≤ n^{1/q})

≥ 1 − Pr (⟨H, a⟩< n^{1/q} \sqrt{\frac{δ logn}{n}} · ∥a∥_{p})− Pr(∥H∥_{q} > n^{1/q})

≥^{(8)} Pr (⟨H, a⟩≥ n^{1/q} \sqrt{\frac{δ logn}{n}} · ∥a∥_{p})− e^{−n/8}.  (9)

As in the proof of Lemma 3.2 we write X = ∑ _{j=1}^{n} a_{j}h_{j}. Let

S \{j ∈ \{1, …, n\} : |a_{j}| ≤ \frac{2^{\frac{1}{2−p}} ∥a∥2^{\frac{2}{2−p}}}{∥a∥p^{\frac{p}{2−p}}} \}.

Then, using the definition of S and Hölder’s inequality, we see that

∥a∥_{p}^{p} = ∑_{j S} |a_{j}|^{p} + ∑_{j∈S} |a_{j}|^{p} ≤ \frac{∥a∥_{p}^{p}}{2∥a∥_{2}^{2}} ∑_{j S} a_{j}^{2} + |S|^{\frac{2−p}{2}} (∑_{j∈S} a_{j}^{2})^{\frac{p}{2}} ≤ \frac{∥a∥_{p}^{p}}{2}+ n^{\frac{2−p}{2}} (∑_{j∈S} a_{j}^{2})^{\frac{p}{2}} .

It follows that

\sqrt{∑_{j∈S} a_{j}^{2}} ≥ \frac{∥a∥_{p}}{2^{\frac{1}{p}}n^{\frac{1}{p}− \frac{1}{2}}} .  (10)

Set Y ∑ _{j∈S} a_{j}h_{j}, and note that

\sqrt{Y^{2}} = \sqrt{∑_{j∈S} a_{j}^{2} h_{j}^{2}} = Ω(1) \sqrt{∑_{j∈S} a_{j}^{2}} ≥^{(10)} c\frac{∥a∥_{p}}{n^{\frac{1}{p}− \frac{1}{2}}},  (11)

where c > 0 is a universal constant. Using the Berry-Esseen inequality as in the proof of Lemma 3.2, we see that

Pr (∑_{j=1}^{n} a_{j}h_{j} ≥ n^{\frac{1}{q}} \sqrt{\frac{δ logn}{n}} · ∥a∥_{p})≥ \frac{1}{2} Pr ( \frac{Y}{\sqrt{Y^{2}}} ≥ 2cn^{1− \frac{1}{p}} \sqrt{\frac{δ logn}{n}} · n^{\frac{1}{p}− \frac{1}{2}} )

≥ \frac{1}{6n^{4c^{2}δ}} − max_{j∈S} \frac{|a_{j}|}{\sqrt{∑ _{k∈S} a_{k}^{2}}} · |h_{1}|^{3} = \frac{1}{6n^{4c^{2}δ}} − O (n^{\frac{1}{p}− \frac{1}{2}} (\frac{∥a∥_{2}}{∥a∥_{p}})^{\frac{2}{2−p}} )≥ \frac{1}{12n^{4c^{2}δ}}, (12)

provided that

n^{\frac{1}{p}− \frac{1}{2}} (\frac{∥a∥_{2}}{∥a∥_{p}})^{\frac{2}{2−p}} ≤ \frac{c̃}{n^{4c^{2}δ}},  (13)

for some small enough constant c̃. But, assuming that (13) fails, and that δ is small enough and n is large enough, we may apply the Paley-Zygmund inequality to conclude that

Pr (∑_{j=1}^{n} a_{j}h_{j} ≥ n^{\frac{1}{q}} \sqrt{\frac{δ logn}{n}} · ∥a∥_{p})≥ Pr(X^{2} ≥ \frac{c̃^{2−p}δ logn}{n^{2− \frac{p}{2}− \frac{1}{p}−8c^{2}δ}} · X^{2})≥ Pr(X^{2} ≥ \frac{δ logn}{n^{\frac{1}{2}−8c^{2}δ}} · X^{2})≥ Ω(1), (14)

where we used the fact that p ∈ (1, 2) and the easy bound \sqrt[4]{X^{4}} = O ( \sqrt{X^{2}}). Combining (12) and (14) with (9) yields the required result.

Now, arguing as in the proof of Theorem 3.1, given a 0-symmetric convex body K ⊆ ^{n} with a weak optimization oracle, we select m i.i.d. copies of H, H_{1}, …, H_{m}, and define

Alg(K) 2 max_{1≤i≤m} max_{a∈K}⟨\frac{H_{i}}{∥H_{i}∥_{q}}, a⟩.

Arguing as in the proof of Theorem 3.1, with Lemma 3.2 replaced by Lemma 3.3, we see that for m = poly(n), with constant probability

Ω(1) \sqrt{\frac{logn}{n}} · diam_{p}(K) ≤ Alg(K) ≤ diam_{p}(K).

4 Discussion and open problems

We end this paper with some remarks and directions for future research.

• We assumed throughout that a_{iik} = a_{ijj} = a_{iji} = 0. This restriction, which also appeared in [2] as the condition that the Fourier support graph does not have self loops, is necessary since otherwise if P NP then there is no polynomial time algorithm that evaluates the maximum of ∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} over x ∈ {−1, 1}^{n} up to any factor (even one that grows with n arbitrarily fast)—see the discussion in Remark 3.2 in [2].

• It would be interesting to investigate maximization problem of ∑ _{i,j,k=1}^{n} a_{ijk}x_{i}x_{j}x_{k} in terms of the combinatorial structure of the Fourier support hypergraph given by {{i, j, k} : a_{ijk} 0}. The results of [2] suggest that it might be possible to achieve a better approximation guarantee in the presence of additional structural information of this type.

• A natural question that arises from our results is to study the maximization problem for

∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}}a_{S} ∏_{j∈S} x_{j}

when k ≥ 4. Our methods do not immediately give good bounds in this case—it is quite easy to get a

O (\frac{n^{\frac{k}{2}−1}}{(logn)^{\frac{k}{2}−1}}) approximation algorithm for odd k by iterating our approach, and it would be desirable to

get improved bounds. Such improvements, beyond their intrinsic interest, might have implications to the problem of refutation of random k − CNF formulas [16, 15, 14] (see [13] for motivation of such questions). The connection between these two problems is explained in the following theorem.

Theorem 4.1. Suppose for every ℓ ∈ {1, …, k} there is a deterministic polynomial time algorithm that approximates

max_{x_{1},x_{2},...,xn∈\{−1,1\}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=ℓ \end{matrix}}a_{S} ∏_{j∈S} x_{j}

within factor f (n). Then there is a polynomial time refutation procedure that refutes w.h.p. a random k-CNF formula with 2^{4k+1}nf (n)^{2} clauses.

Remark 4.1. Note that for ℓ = 1, there is a (trivial) exact algorithm and for ℓ = 2 the result of [27, 25, 12] give a O(logn)-approximation. Therefore, as long as f (n) ≥ O(logn), the hypothesis in Theorem 4.1 is required to hold only for 3 ≤ ℓ ≤ k.

The best known refutation procedure for random 3 − CNF formulas works when they have O (n^{3/2}) clauses [16]. This can be viewed as evidence that obtaining an improvement over our approximation factor to o (n^{1/4})is likely to be difficult.

Before proving Theorem 4.1 we shall introduce some notation. Let −1 represent logical TRUE and 1 represent logical FALSE. Let ϕ = {C_{1}, C_{2}, …, C_{m}} be a k-CNF formula on variables x := {x_{1}, x_{2}, …, x_{n}}. Let the set of indices of variables in the clause C_{i} be denoted as S_{i}, so that |S_{i}| = k. Define {σ_{ij} : 1 ≤ i ≤ m, j ∈ S_{i}} as follows: σ_{ij} = 1 if x_{j} appears in clause C_{i} un-negated and σ_{ij} = −1 if x_{j} appears in clause C_{i} negated. Consider the expression

1 − \frac{1}{2^{k}} ∏_{j∈S_{i}} (1 + σ_{ij}x_{j}) .

For any {−1, 1}-assignment to variables, this expression evaluates to 1 if the clause C_{i} is satisfied and to 0 if the clause C_{i} is not satisfied. Therefore, the fraction of satisfied clauses is

\frac{1}{m} ∑_{i=1}^{m} (1 − \frac{1}{2^{k}} ∏_{j∈S_{i}} (1 + σ_{ij}x_{j}) ) .  (15)

For notational convenience, think of S_{i} as an ordered k-tuple of indices, and for T ⊆ {1, …, k}, let S_{i}[T] denote the subset of S_{i} given by the co-ordinates in T. With this notation (15) can be rewritten as

1 − \frac{1}{2^{k}} − \frac{1}{m} ∑_{i=1}^{m} ∑_{∅ T⊆\{1,...,k\}} ∏_{j∈S_{i}[T]} σ_{ij}x_{j} = 1 − \frac{1}{2^{k}} + ∑_{∅ T⊆\{1,...,k\}}Γ_{T}(x),  (16)

Where

Γ_{T}(x) −\frac{1}{m} ∑_{i=1}^{m} ∏_{j∈S_{i}[T]} σ_{ij}x_{j}.  (17)

Lemma 4.2. If ϕ is satisfiable, then there exists a {−1, 1} assignment to variables of ϕ and a nonempty set T ⊆ \{1, …k\} such that Γ_{T}(x) ≥ \frac{1}{2^{k}(2^{k}−1)} . In other words,

∃ ∅ T ⊆ \{1, …, k\}, max_{x∈\{−1,1\}^{n}}Γ_{T}(x) ≥ \frac{1}{2^{k}(2^{k} − 1)} .

Proof. Since ϕ is satisfiable, there is an assignment x that satisfies every clause. For this assignment, the expression (16) has value 1. Thus, for some T ⊆ [k], T ∅, it must be the case that Γ_{T}(x) ≥ \frac{1}{2^{k}(2^{k}−1)} .

Lemma 4.3. Let ϕ be a random k-CNF formula with m ≥ 2^{4k+1}nf (n)^{2} clauses. Then with probability 1 − 2^{−Ω(n)} over the choice of the formula, for every {−1, 1}-assignment to variables and every nonempty T ⊆ \{1, …, k\} we have Γ_{T}(x) ≤ \frac{1}{2^{2k}f (n)}. In other words,

∀∅ T ⊆ \{1, …, k\}, max_{x∈\{−1,1\}^{n}}Γ_{T}(x) ≤ \frac{1}{2^{2k}f (n)}.

Proof. Fix any {−1, 1}-assignment to the variables and a nonempty set T ⊆ {1, …, k}. We will show that with probability 1 − e^{−n} over the choice of ϕ we have Γ_{T}(x) ≤ \frac{1}{2^{2k}f (n)}. Taking the union bound over all possible {−1, 1}-assignments to variables and all choices for T implies the statement of the lemma.

Note that when ϕ is random, the signs σ_{ij} are random and independent, and therefore an inspection of the definition (17) shows that Γ_{T}(x) is an average of m independent Bernoulli random variables. By the Chernoff bound,

Pr[Γ_{T}(x) ≥ \frac{1}{2^{2k}f (n)}] ≤ exp(−\frac{1}{2} · \frac{m}{(2^{2k}f (n))^{2}} )≤ e^{−n}.

Proof of Theorem 4.1. The refutation procedure is very simple. Given a formula ϕ, use the f (n)-approximation algorithm to compute, for every nonempty T ⊆ {1, …, k}, a number Alg(Γ_{T}) such that

\frac{1}{f (n)} ( max_{x∈\{−1,1\}^{n}}Γ_{T}(x)) ≤ Alg(Γ_{T}) ≤ max_{x∈\{−1,1\}^{n}}Γ_{T}(x).

If there is some T ∅ for which Alg(Γ_{T}) ≥ \frac{1}{2^{k}(2^{k}−1)f (n)} , then say YES. Otherwise, say NO. Lemma 4.2 shows that this procedure always says YES if ϕ is satisfiable. Lemma 4.3 shows that the procedure says NO on a 1 − 2^{−Ω(n)} fraction of random formulas.

References

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

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

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

[4] N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, second edition, 2000. With an appendix on the life and work of Paul Erdős.

[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] I. Bárány and Z. Füredi. Computing the volume is difficult. Discrete Comput. Geom., 2(4):319–326, 1987.

[7] F. Barthe, M. Csörnyei, and A. Naor. A note on simultaneous polar and Cartesian decomposition. In Geometric aspects of functional analysis, volume 1807 of Lecture Notes in Math., pages 1–19. Springer, Berlin, 2003.

[8] H. L. Bodlaender, P. Gritzmann, V. Klee, and J. van Leeuwen. Computational complexity of normmaximization. Combinatorica, 10(2):203–225, 1990.

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

[10] A. Brieden, P. Gritzmann, R. Kannan, V. Klee, L. Lovász, and M. Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48(1-2):63–105 (2003), 2001.

[11] B. Carl and A. Pajor. Gel′fand numbers of operators with values in a Hilbert space. Invent. Math., 94(3):479–504, 1988.

[12] 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.

[13] U. Feige. Relations between average case complexity and approximation complexity. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 534–543 (electronic), New York, 2002. ACM.

[14] U. Feige, J. H. Kim, and E. Ofek. Witnesses for non-satisfiability of dense random 3CNF formulas. In 47th Annual Symposium on Foundations of Computer Science, pages 497–508. IEEE Computer Society, 2006.

[15] U. Feige and E. Ofek. Easily refutable subformulas of large random 3CNF formulas. In Automata, languages and programming, volume 3142 of Lecture Notes in Comput. Sci., pages 519–530. Springer, Berlin, 2004.

[16] J. Friedman, A. Goerdt, and M. Krivelevich. Recognizing more unsatisfiable random k-SAT instances efficiently. SIAM J. Comput., 35(2):408–430 (electronic), 2005.

[17] E. D. Gluskin. Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces. Mat. Sb. (N.S.), 136(178)(1):85–96, 1988.

[18] P. Gritzmann and V. Klee. Computational convexity. In Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., pages 491–515. CRC, Boca Raton, FL, 1997.

[19] 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.

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

[21] J. H�stad. Some optimal inapproximability results. J. ACM, 48(4):798–859 (electronic), 2001.

[22] J. H�stad and S. Venkatesh. On the advantage over a random assignment. Random Structures Algorithms, 25(2):117–149, 2004.

[23] J.-P. Kahane. Some random series of functions, volume 5 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 1985.

[24] 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.

[25] 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.

[26] A. Naor. The surface measure and cone measure on the sphere of l_{p}^{n}. Trans. Amer. Math. Soc., 359(3):1045–1079 (electronic), 2007.

[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] R. Paley and A. Zygmund. A note on analytic functions in the unit circle. Proc. Camb. Phil. Soc., 28:266–272, 1932.

[29] G. Schechtman and J. Zinn. On the volume of the intersection of two L_{p}^{n} balls. Proc. Amer. Math. Soc., 110(1):217–224, 1990.

[30] 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.

[31] K. Varadarajan, S. Venkatesh, and J. Zhang. On approximating the radii of point sets in high dimensions. In 43rd Annual Symposium on Foundations of Computer Science, pages 561–569. IEEE Computer Society, 2002.