Approximating the Cut-Norm via Grothendieck’s Inequality

Draft

Noga Alon ^{∗}  Assaf Naor ^{†}

Abstract The cut-norm ||A||_{C} of a real matrix A = (a_{ij})_{i∈R,j∈S} is the maximum, over all I ⊂ R, J ⊂ S of the quantity | ∑_{i∈I,j∈J} a_{ij}|. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and provide an efficient approximation algorithm. This algorithm finds, for a given matrix A = (a_{ij})_{i∈R,j∈S}, two subsets I ⊂ R and J ⊂ S, such that | ∑_{i∈I,j∈J} a_{ij}| ≥ ρ||A||_{C}, where ρ > 0 is an absolute constant satisfying ρ > 0.56. The algorithm combines semidefinite programming with a novel rounding technique based on Grothendieck’s Inequality.

1 Introduction

The cut-norm ||A||_{C} of a real matrix A = (a_{ij})_{i∈R,j∈S} with a set of rows indexed by R and a set of columns indexed by S is the maximum, over all I ⊂ R, J ⊂ S, of the quantity | ∑_{i∈I,j∈J} a_{ij}|. This concept plays a major role in the work of Frieze and Kannan on efficient approximation algorithms for dense graph and matrix problems, [7] (see also [2] and its references). Although the techniques in [7] enable the authors to approximate efficiently the cut-norm of an n by m matrix with entries in [−1, 1] up to an additive error of ϵnm, there is no known polynomial algorithm that approximates the cut-norm of a general real matrix up to a constant multiplicative factor.

Let CUT NORM denote the computational problem of computing the cut-norm of a given real matrix. Here we first observe that the CUT NORM problem is MAX SNP hard, and then provide an efficient approximation algorithm for the problem. This algorithm finds, for a given matrix A = (a_{ij})_{i∈R,j∈S}, two subsets I ⊂ R and J ⊂ S, such that | ∑_{i∈I,j∈J} a_{ij}| ≥ ρ||A||_{C}, where ρ > 0 is an absolute constant. We first describe a deterministic algorithm that supplies a rather poor value of ρ, and then describe a randomized algorithm that provides a solution of expected value greater than 0.56 times the optimum.

∗Schools of Mathematics and Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel. Email: noga@math.tau.ac.il. Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

†Microsoft Research, One Microsoft Way 113/2131, Redmond, WA 98052-6399, USA. Email:

anaor@microsoft.com.

The algorithm combines semidefinite programming with a novel rounding technique based on (the proofs of) Grothendieck’s Inequality. This inequality, first proved in [10], is a fundamental tool in Functional Analysis, and has several interesting applications in this area. We will actually use the matrix version of Grothendieck’s inequality, formulated in [19]. In order to apply semidefinite programming for studying the cut-norm of an n by m matrix A = (a_{ij}), it is convenient to first study another norm,

||A||_{∞↦1} = max ∑_{i=1}^{n} ∑_{j=1}^{m} a_{ij}x_{i}y_{j},

where the maximum is taken over all x_{i}, y_{j} ∈ {−1, 1}.

It is not difficult to show (see section 3), that for every matrix A,

4||A||_{C} ≥ ||A||_{∞↦1} ≥ ||A||_{C},

and hence a constant approximation of any of these norms provides a constant approximation of the other.

The value of ||A||_{∞↦1} is given by the following quadratic integer program

Maximize ∑_{ij} a_{ij}x_{i}y_{j}  (1)
subject to x_{i}, y_{j} ∈ {−1, 1} for all i, j.

The obvious semidefinite relaxation of this program is

Maximize ∑_{ij} a_{ij}u_{i} · v_{j}  (2)
subject to ||u_{i}|| = ||v_{j}|| = 1,

where here u_{i} · v_{j} denotes the inner product of u_{i} and v_{j}, which are now vectors of (Euclidean) norm 1 that lie in an arbitrary Hilbert space. Clearly we may assume, without loss of generality, that they lie in an n + m-dimensional space.

This semidefinite program can be solved, using well known techniques (see [9]) within an additive error of ϵ, in polynomial time (in the length of the input and in the logarithm of 1/ϵ.) The main problem is the task of rounding this solution into an integral one. A first possible attempt is to imitate the technique of Goemans and Williamson in [11], that is, given a solution u_{i}, v_{j} to the above program, pick a random vector z and define x_{i} = sign(u_{i} · z) and y_{j} = sign(v_{j} · z). It is easy to check that the expected value of x_{i}y_{j} satisfies E(x_{i}y_{j}) = \frac{2}{π} arcsin(u_{i} · v_{j}), and as arcsin(t) and t differ only in constant factors for all −1 ≤ t ≤ 1, one could hope that this will provide an integral solution whose value is at least some absolute constant fraction of the value of the optimal solution. This reasoning is, unfortunately, incorrect, as some of the entries a_{ij} may be positive and some may be negative, (in fact, the problem is interesting only if this is the case, since otherwise either x_{i} = y_{j} = 1 or x_{i} = −y_{j} = 1 for all i, j supplies the required maximum). Therefore, even if each single term a_{ij}u_{i} · v_{j} is approximated well by its integral rounding a_{ij}x_{i}y_{j}, there is no reason to expect the sum to be well-approximated, due to cancellations. We thus have to compare the value of the rounded solution to that of the semidefinite program on a global basis. Nesterov [21] obtained a result of this form for the problem of approximating the maximum value of a quadratic form ∑_{ij} b_{ij}x_{i}x_{j}, where x_{i} ∈ {−1, 1}, but only for the special case in which the matrix B = (b_{ij}) is positive semidefinite. While his estimate is global, his rounding is the same simple rounding technique of [11] described above. As explained before, some new ideas are required in our case in order to get any nontrivial result.

Luckily, there is a well known inequality of Grothendieck, which asserts that the value of the semidefinite program (2) and that of the integer program (1) can differ only by a constant factor. The precise value of this constant, called Grothendieck’s constant and denoted by K_{G}, is not known, but it is known that its value is at most \frac{π}{2 ln(1+\sqrt{2})} = 1.782... ([17]) and at least \frac{π}{2} = 1.570... ([10]). Stated in other words, the integrability gap of the problem is at most K_{G}. (Krivine mentions in [17] that he can improve the lower bound, but such an improvement has never been published).

It follows that the value of the semidefinite program (2) provides an approximation of ||A||_{∞↦1} up to a constant factor. This, however, still does not tell us how to round the solution of the semidefinite program into an integral one with a comparable value. Indeed, this task requires more work, and is carried out in the following sections.

We describe three rounding techniques. The first one is a deterministic procedure, which combines Grothendieck’s Inequality with some facts about four-wise independent random variables, in a manner that resembles the technique used in [4] to approximate the second frequency moment of a stream of data under severe space constraints. The second rounding method is based on Rietz’ proof of Grothendieck’s Inequality [23]. This proof supplies a better approximation guarantee for the special case of positive semidefinite matrices A, where the integrality gap can be shown to be precisely π/2, and implies that Nesterov’s analysis for the problem he considers in [21] is tight.

The third technique, which supplies the best approximation guarantee, is based on Krivine’s proof of Grothendieck’s Inequality. Here we use the vectors u_{i}, v_{j} which form a solution of the semidefinite program (2) to construct some other unit vectors u′_{i}, v′_{j}, which are first shown to exist in an infinite dimensional Hilbert space, and are then found, using another instance of semidefinite programming, in an n + m-dimensional space. These vectors can now be rounded to {−1, 1} in order to provide an integral solution for the original problem (1) in a rather simple way. We note that there are several known techniques for modifying the solution of a semidefinite program before rounding it, see [25], [18], [8]. Here, however, the modification seems more substantial.

We believe that our techniques will have further applications, as they provide a method for handling problems in which there is a possible cancellation between positive and negative terms. It seems that there are additional interesting problems of this type. Moreover, unlike the semidefinite based approximation algorithms for MAX CUT, MAX 2SAT and related problems, suggested in the seminal paper of [11] and further developed in many subsequent papers, the problem considered here has no known constant approximation algorithm, and the semidefinite programming and its rounding appear to be essential in order to obtain any constant approximation guarantee, and not only in order to improve the constants ensured by appropriate combinatorial algorithms.

The rest of this paper is organized as follows. In Section 2 we present the (relatively simple) proof that the problem of approximating the cut-norm ||A||_{C}, as well as the related problem of approximating ||A||_{∞↦1}, are both MAX SNP hard. In Section 3 we describe a deterministic procedure that approximates the cut-norm of a given matrix up to a constant factor. Two other methods, providing better constants, are described in Section 4, where we also consider the special case of positive semidefinite matrices. We conclude with Section 5, that includes some applications, concluding remarks and open problems.

2 Hardness of approximation

As usual, we say that an approximation algorithm for a maximization problem has performance ratio or performance guarantee ρ for some real ρ ≤ 1, if it always delivers a solution with objective function value at least ρ times the optimum value. Such an approximation algorithm is then called a ρ-approximation algorithm. Similarly, a randomized approximation algorithm is a ρ−approximation algorithm if it always produces a solution with expected value at least ρ times the optimum.

In this section we observe that the problem of approximating the cut-norm ||A||_{C} of a given input matrix is MAX SNP hard, and so is the related problem of approximating ||A||_{∞↦1}. This implies, by the results in [22], [6], that there exists some ρ < 1 such that the existence of a ρapproximation, polynomial-time algorithm for any of these problems would imply that P = NP. The proof is by a reduction of the MAX CUT problem to the CUT NORM problem, and to the problem of computing ||A||_{∞↦1}. We need the following simple observation.

Lemma 2.1 For any real matrix A = (a_{ij}),

||A||_{C} ≤ ||A||_{∞↦1} ≤ 4||A||_{C}.

Moreover, if the sum of each row and the sum of each column of A is zero, then ||A||_{∞↦1} = 4||A||_{C}.

Proof: For any x_{i}, y_{j} ∈ {−1, 1},

∑_{i,j} a_{ij}x_{i}y_{j} = ∑_{i:x_{i}=1,j:x_{j}=1} a_{ij} − ∑_{i:x_{i}=1,j:x_{j}=−1} a_{ij} − ∑_{i:x_{i}=−1,j:x_{j}=1} a_{ij} + ∑_{i:x_{i}=−1,j:x_{j}=−1} a_{ij}.

The absolute value of each of the four terms in the right hand side is at most ||A||_{C}, implying, by the triangle inequality, that

||A||_{∞↦1} ≤ 4||A||_{C}.  (3)

Suppose, now, that ||A||_{C} = ∑_{i∈I,j∈J} a_{ij} (the computation in case it is − ∑_{i∈I,j∈J} a_{ij} is essentially the same). Define x_{i} = 1 for i ∈ I and x_{i} = −1 otherwise, and similarly, y_{j} = 1 if j ∈ J and y_{j} = −1 otherwise. Then

||A||_{C} = ∑_{i,j} a_{ij} \frac{1 + x_{i}}{2} \frac{1 + y_{j}}{2} = \frac{1}{4} ∑_{i,j} a_{ij} + \frac{1}{4} ∑_{i,j} a_{ij}x_{i} · 1 + \frac{1}{4} ∑_{i,j} a_{ij}1 · y_{j} + \frac{1}{4} ∑_{i,j} a_{ij}x_{i}y_{j}.

The absolute value of each of the four terms in the right hand side is at most ||A||_{∞↦1}/4, implying that ||A||_{∞↦1} ≥ ||A||_{C}. If the sum of each row and the sum of each column of A is zero, then the right hand side is precisely \frac{1}{4} ∑_{i,j} a_{ij}x_{i}y_{j}, implying that in this case |A||_{∞↦1} ≥ 4||A||_{C}, which, in view of (3), shows that the above holds as an equality. □

Proposition 2.2 Given a (weighted or unweighted) graph G = (V, E), there is an efficient way to construct a real 2|E| by |V | matrix A, such that

MAXCUT (G) = ||A||_{C} = ||A||_{∞↦1}/4.

Therefore, the CUT NORM problem and the problem of computing ||A||_{∞↦1} are both MAX SNP hard.

Proof: We describe the construction for the unweighted case. The weighted case is similar. Given G = (V, E), orient it in an arbitrary manner. Let V = {v_{1}, v_{2}, …, v_{n}} and E = {e_{1}, e_{2}, …, e_{m}}, and let A = (a_{ij}) be the 2m by n matrix defined as follows. For each 1 ≤ i ≤ m, if e_{i} is oriented from v_{j} to v_{k}, then a_{2i−1,j} = a_{2i,k} = 1 and a_{2i−1,k} = a_{2i,j} = −1. The rest of the entries of A are all 0. It is not difficult to check that MAXCUT (G) = ||A||_{C}. In addition, since the sum of entries in each row and in each column of A is zero, it follows by Lemma 2.1 that ||A||_{∞↦1} = 4||A||_{C}. As it is known [22], [13] that the MAX CUT problem is MAX SNP hard, the desired result follows. □

Håstad [13] has shown that if P ≠ NP then there is no polynomial time approximation algorithm for the MAX CUT problem with approximation ratio exceeding 16/17. Thus, this is an upper bound for the best possible approximation guarantee of a polynomial algorithm for approximating ||A||_{C} or ||A||_{∞↦1}. Similarly, our reduction above can be easily modified to construct, for any given directed graph D, a matrix B with vanishing row sums and column sums, so that the value of the maximum directed cut of D is equal to ||B||_{C}. Håstad [13] has shown that if P ≠ NP then there is no polynomial time approximation algorithm for the MAX DICUT problem with approximation ratio exceeding 12/13. Thus, this is an upper bound for the best possible approximation guarantee of a polynomial approximation algorithm for ||B||_{C} or ||B||_{∞↦1}.

3 Approximating the cut-norm

In this section we describe an efficient, deterministic, ρ- approximation algorithm for the CUT NORM problem, where ρ > 0 is an absolute constant. We make no attempt here to optimize the value of ρ: this will be done (in a different way) in Section 4. We believe, however, that although the value of ρ obtained in this section is rather poor, the method, which is motivated by the proof Grothendieck’s inequality in [15], is interesting and may lead to similar results for related problems.

Given a real n by m matrix A = (a_{ij}), our objective is to find x_{i}, y_{j} ∈ {−1, 1}, such that

∑_{i,j} a_{ij}x_{i}y_{j} ≥ ρ||A||_{∞↦1},

where ρ is an absolute positive constant. The discussion in Section 1 and the proof of Lemma 2.1 imply that this will yield a similar procedure for finding I and J such that | ∑_{i∈I,j∈J} a_{ij}| ≥ ρ′||A||_{C}.

We start by solving the semidefinite program (2). We can thus compute, for any positive δ, unit vectors u_{i}, v_{j} ∈ R^{p}, where p = n + m, such that the sum ∑_{i,j} a_{ij}u_{i} · v_{j} is at least the maximum value of the program (2) (which is clearly at least ||A||_{∞↦1}) minus δ. Since the value of the above norm of A is at least the maximum absolute value of an entry of A, we can make sure that the δ term is negligible. The main part of the algorithm is the rounding phase, that is, the phase of finding, using the vectors u_{i}, v_{j}, reals x_{i}, y_{j} ∈ {−1, 1}, such that

∑_{i,j} a_{ij}x_{i}y_{j} ≥ ρ ∑_{i,j} a_{ij}u_{i} · v_{j}.

This is done as follows. Let V be an explicit set of t = O(p^{2}) vectors ϵ = (ϵ_{1}, ϵ_{2}, …, ϵ_{p}) ∈ {−1, 1}^{p} in which the values ϵ_{j} are four-wise independent and each of them attains the two values −1 and 1 with equal probability. This means that for every four distinct coordinates 1 ≤ i_{1} < … < i_{4} ≤ n and every choice of ϵ_{1}, …, ϵ_{4} ∈ {−1, 1}, exactly a (1/16)−fraction of the vectors have ϵ_{j} in their coordinate number i_{j} for j = 1, …, 4. As described, for example, in [1] or [5] such sets (also known as orthogonal arrays of strength 4) can be constructed efficiently using the parity check matrices of BCH codes.

Let M > 0 be a fixed real, to be chosen later. Consider V as a sample space in which all t points ϵ have the same probability. For any unit vector q = (q_{1}, q_{2} …, q_{p}) ∈ R^{p}, let H(q) denote the random variable defined on the sample space V by putting [H(q)](ϵ) = ∑_{j=1}^{p} ϵ_{j}q_{j}. Since the entries ϵ_{j} are four-wise (and hence pairwise) independent, it follows that for any two vectors q, q′, the expectation of H(q)H(q′) is precisely the inner product q · q′. In particular, the expectation of [H(q)]^{2} is q · q = 1. Similarly, four-wise independence implies that the expectation of [H(q)]^{4} satisfies

E([H(q)]^{4}) = ∑_{j=1}^{p} q_{j}^{4} + 6 ∑_{1≤j<j′≤p} q_{j}^{2}q_{j′}^{2} ≤ 3 (∑_{j} q_{j}^{2})^{2} = 3.

The M-truncation of H(q), denoted H^{M}(q), is defined as follows: [H^{M}(q)](ϵ) = [H(q)](ϵ) if |[H(q)](ϵ)| ≤ M, [H^{M}(q)](ϵ) = M if [H(q)](ϵ) > M, and [H^{M}(q)](ϵ) = −M if [H(q)](ϵ) < −M.

By Markov’s Inequality, for every positive real m, P rob[ |H(q)| ≥ m]m^{4} ≤ E([H(q)]^{4}) ≤ 3, implying that P rob[ |H(q)| ≥ m] ≤ \frac{3}{m^{4}} . This implies the following

Claim 3.1 The expectation E(|H(q) − H^{M}(q)|^{2}) satisfies

E(|H(q) − H^{M}(q)|^{2}) ≤ \frac{1}{M^{2}} .

□

Each random variable H(q) can be associated with a vector h(q) ∈ R^{t} by defining [h(q)](ϵ) = \frac{1}{\sqrt{t}}[H(q)](ϵ). The truncation h^{M}(q) = H^{M}(q)/\sqrt{t} is defined analogously. The above discussion thus implies the following.

Lemma 3.2 For each unit vector q ∈ R^{p}, h(q) ∈ R^{t} is a unit vector. The norm of h^{M}(q) is at most 1, and that of h(q) − h^{M}(q) is at most 1/M. If q′ ∈ R^{p} is another vector, then h(q) · h(q′) = q · q′. □

Returning to our semidefinite program (2) and its solution (up to δ) given by the vectors u_{i}, v_{j} ∈ R^{p}, let B denote the value of the program. Since h(q) · h(q′) = q · q′ for all unit vectors q, q′, it follows that

B − δ ≤ ∑_{ij} a_{ij}u_{i} · v_{j} = ∑_{ij} a_{ij}h(u_{i}) · h(v_{j})

= ∑_{ij} a_{ij}h^{M}(u_{i}) · h^{M}(v_{j}) + ∑_{ij} a_{ij}(h(u_{i}) − h^{M}(u_{i})) · h^{M}(v_{j}) + ∑_{ij} a_{ij}h(u_{i}) · (h(v_{j}) − h^{M}(v_{j})).

By the convexity of the program, and since the norm of each vector h^{M}(v_{j}), h(u_{i}) is at most 1, and the norm of each vector h(u_{i}) − h^{M}(u_{i}) and each vector h(v_{j}) − h^{M}(v_{j}) is at most 1/M, it follows that

∑_{ij} a_{ij}(h(u_{i}) − h^{M}(u_{i})) · h^{M}(v_{j}) + ∑_{ij} a_{ij}h(u_{i}) · (h(v_{j}) − h^{M}(v_{j})) ≤ \frac{2}{M} B.

Here we have used, crucially, the fact that as B is the maximum value of the semidefinite program, its value on the vectors h(u_{i}) − h^{M}(u_{i}) and the vectors h(v_{j}) does not exceed B \frac{1}{M}, and so does its value on the vectors h(u_{i}) and h(v_{j}) − h^{M}(v_{j}). Therefore,

B(1 − \frac{2}{M}) − δ ≤ ∑_{ij} a_{ij}h^{M}(u_{i}) · h^{M}(v_{j}).

It follows that there is a coordinate ϵ ∈ V such that

∑_{ij} a_{ij}h^{M}(u_{i})(ϵ) · h^{M}(v_{j})(ϵ) ≥ \frac{1}{t} (B (1 − \frac{2}{M} ) − δ) .

By the definition of the vectors h, this implies

∑_{ij} a_{ij}H^{M}(u_{i})(ϵ) · H^{M}(v_{j})(ϵ) ≥ B (1 − \frac{2}{M} ) − δ.

Choose M = 3 and define x_{i} = H^{M}(u_{i})(ϵ)/M, y_{j} = H^{M}(v_{j})(ϵ)/M. Then x_{i}, y_{j} are reals, each having an absolute value at most 1, and

∑_{ij} a_{ij}x_{i}y_{j} ≥ B (\frac{M − 2}{M^{3}}) − \frac{δ}{M^{2}} = \frac{B}{27} − \frac{δ}{9}.

Fixing all x_{i}, y_{j} but, say, x_{1}, the left hand side is a linear form in x_{1}, and thus we can shift x_{1} to either −1 or 1, without any decrease in the value of the sum. Proceeding in this way with the other variables, each one in its turn, we obtain x_{i}, y_{j} ∈ {−1, 1} such that the value of the sum ∑_{ij} a_{ij}x_{i}y_{j} is at least \frac{B}{27} − \frac{δ}{9}. As δ is arbitrarily small, we have thus proved the following.

Theorem 3.3 There is a deterministic polynomial time algorithm that finds, for a given real matrix A = (a_{ij}), integers x_{i}, y_{j} ∈ {−1, 1} such that the value of the sum ∑_{ij} a_{ij}x_{i}y_{j} is at least 0.03 B, where B is the value of the semidefinite program (2) (which is at least ||A||_{∞↦1}). □

4 Improving the constant

The constant obtained in the previous section can be improved by replacing the space V of fourwise independent {−1, 1} variables with a space of 2k-wise independent {−1, 1} variables (or with a space of independent standard normal random variables). This, however, will not provide a ρ-approximation algorithm with ρ > \frac{1}{5}.

In fact, we can do much better. In this section we describe two randomized ρ-approximation algorithms for approximating ||A||_{∞↦1}. For the first algorithm, ρ = \frac{4}{π} − 1 > 0.27, while for the second ρ = ^{\frac{2 ln(1+\sqrt{2})}{π}} > 0.56. We further show that these yield randomized ρ-approximation algorithms for the CUT NORM problem, with the same values of ρ (without losing the factor of 4 that appears in Lemma 2.1.) It should be possible to derandomize these algorithms using the techniques of [20].

4.1 Averaging with a Gaussian measure

The main idea here, based on [23], is to round the solution u_{i}, v_{j} ∈ R^{p} of the semidefinite program (2) by averaging over R^{p} with normalized Gaussian measure. We proceed with the details.

Let g_{1}, g_{2}, …, g_{p} be standard, independent, Gaussian random variables, and consider the random vector G = (g_{1}, …, g_{p}). The following identity holds for every two unit vectors b, c ∈ ℓ_{2}^{p}:

\frac{π}{2} E [sign(b · G) · sign(c · G)] = b · c + E \{[b · G − \sqrt{\frac{π}{2}} sign(b · G)] · [c · G − \sqrt{\frac{π}{2}} sign(c · G)]\} (4)

This is a simple exercise, using rotation invariance. Indeed, the fact that

E [(b · G)(c · G)] = b · c  (5)

follows from the orthogonality of the vectors g_{i}; if b = (b_{1}, …, b_{p}) and c = (c_{1}, …, c_{p}), then

E [(b · G)(c · G)] = E [∑_{i=1}^{p} b_{i}g_{i} ∑_{i=1}^{p} c_{i}g_{i}] = ∑_{i,j} b_{i}c_{j}E[g_{i}g_{j}] = ∑_{i=1}^{p} b_{i}c_{i} = b · c.

To compute E [(b · G)sign(c · G)] assume, by rotation invariance, that c = (1, 0, …, 0), and b = (b_{1}, b_{2}, 0, …, 0). Hence b · c = b_{1} and

E [(b · G)sign(c · G)] = E [(b_{1}g_{1} + b_{2}g_{2})sign(g_{1})] = E [(b_{1}g_{1}sign(g_{1})] + E[b_{2}g_{2}]E[sign(g_{1})]

= E [(b_{1}g_{1}sign(g_{1})] = 2 ∫_{0}^{∞} \frac{1}{\sqrt{2π}} b_{1}xe^{−x^{2}/2}dx = \sqrt{\frac{2}{π}} b_{1}.

Thus

E [(b · G)sign(c · G)] = \sqrt{\frac{2}{π}} b · c.  (6)

The identity above follows from (5) and (6), by linearity of expectation.

Suppose, now, that the vectors u_{i}, v_{j} ∈ R^{p} supply a solution of (2), which can be found efficiently (we assume, for simplicity, that this is a precise solution). Let B denote the value of the solution. By (4)

\frac{π}{2} E \{∑_{i,j} a_{ij} [sign(u_{i} · G) · sign(v_{j} · G)]\}
= B + ∑_{i,j} a_{ij}E \{[u_{i} · G − \sqrt{\frac{π}{2}} · sign(u_{i} · G)] · [v_{j} · G − \sqrt{\frac{π}{2}} · sign(v_{j} · G)]\} .  (7)

Note that each term of the form

E \{[u_{i} · G − \sqrt{\frac{π}{2}} · sign(u_{i} · G)] · [v_{j} · G − \sqrt{\frac{π}{2}} · sign(v_{j} · G)]\}

which multiplies a_{ij} in (7), is the inner product of two vectors in a Hilbert space. Moreover, the square of the norm of each of these vectors is easily seen to be \frac{π}{2} − 1, by substituting b = c = u_{i} (or b = c = v_{j}) in (4). Therefore, as B is the maximum possible value of the program (2), it follows that the last sum in (7) is bounded, in absolute value, by (\frac{π}{2} − 1)B. Thus, by (7)

\frac{π}{2} E \{∑_{i,j} a_{ij} [sign(u_{i} · G) · sign(v_{j} · G)]\} ≥ (2 − \frac{π}{2} ) B,

implying that by choosing the normal random variables g_{i} randomly, and by defining

x_{i} = sign(u_{i} · G), y_{j} = sign(v_{j} · G)

we get a solution for (1) whose expected value is at least \frac{2}{π} (2 − \frac{π}{2} )B = (\frac{4}{π} − 1)B. As B is at least the value of the optimal solution of (1), this supplies a randomized ρ-approximation algorithm for estimating ||A||_{∞↦1}, where ρ = \frac{4}{π} − 1. Remark: The above algorithm is based only on the basic idea in the proof of [23], and it is in fact possible to improve its performance guarantee by modifying it according to the full proof. This suggests to round u_{i} · G to x_{i} = sign(u_{i} · G) if it is ”large”, and to round it to some multiple of u_{i} · G if it is not, where the definition of ”large” and the precise multiple are chosen optimally. We can then further round the fractional values of x_{i} to integral ones with no loss. This resembles some of the ideas used in several recent papers including [25], [18] and [8]. We do not include the details here, as we can get a better approximation guarantee, using another method, described in subsection 4.3.

4.2 Positive semidefinite matrices

In this section we observe that when A = (a_{ij}) is positive semidefinite then the approximation ratio can be improved to 2/π. This follows from the work of Nesterov [21], but the short argument we describe here is based on Rietz’ proof that for such an A the constant in Grothendieck’s Inequality can be improved to π/2. Grothendieck himself showed in [10] (in a somewhat different language) that π/2 is a lower bound for the constant in this case; we sketch a proof of this fact below.

We first show that if A = (a_{ij}) is a positive semidefinite n by n matrix, then the maximum of the semidefinite program (2) is obtained for some vectors u_{i}, v_{j} satisfying u_{i} = v_{i} for all i (though, of course, it may also be obtained for some vectors that do not satisfy this property). This is not really required for getting the 2/π approximation algorithm, but we include this proof as it shows that the integrality gap of the problem is at most π/2.

Suppose, thus, that the maximum value of (2), denoted by B, is obtained by some p-dimensional vectors, where p ≤ 2n and A is positive semidefinite. Let D = A ⊗ I be the tensor product of A with a p by p identity matrix. This is simply the np by np matrix consisting of p blocks along the diagonal, each being a copy of A. Given u_{1}, …, u_{n} ∈ ℓ_{2}^{p}, where u_{i} = (u_{i1}, u_{i2}, …, u_{ip}) let u^{(j)} = (u_{1j}, u_{2j}, …, u_{nj}) be the vector consisting of the j-th coordinates of all vectors u_{i}, (1 ≤ j ≤ p). Let u = (u^{(1)}, u^{(2)}, …, u^{(p)}) ∈ ℓ_{2}^{np} and note that Du = (Au^{(1)}, Au^{(2)}, …, Au^{(p)}). Thus D is positive semidefinite and for u_{1}, …, u_{n}, v_{1}, …, v_{n} ∈ ℓ_{2}^{p},

∑_{i,j} a_{ij}u_{i} · v_{j} = Du · v = D^{1/2}u · D^{1/2}v ≤ ∥D^{1/2}u∥ · ∥D^{1/2}v∥,

with equality when u = v.

Therefore, if the maximum B of the quantity ∑_{i,j} a_{ij}u_{i} · v_{j} is obtained for the unit vectors u_{i}, v_{j} ∈ ℓ_{2}^{p}, then, as ∥D^{1/2}u∥ cannot exceed B^{1/2}, it follows that ∥D^{1/2}u∥ = ∥D^{1/2}v∥ = B^{1/2}. Thus the maximum is also equal to ∑_{i,j} a_{ij}u_{i} · u_{j} (and to ∑_{i,j} a_{ij}v_{i} · v_{j}).

The fact that for positive semidefinite matrices A we can get a ρ-approximation algorithm with ρ = \frac{2}{π} is now an easy consequence of (7). We first solve the semidefinite program (2) to get vectors u_{i}, v_{j} optimizing it. By the above discussion, the vectors u_{i} = v_{i} for all i also give an optimal solution. (Alternatively, we can solve the variant of (2) in which u_{i} = v_{i} for all i directly, and proceed from there.) By (7)

\frac{π}{2} E \{∑_{i,j} a_{ij} [sign(u_{i} · G) · sign(u_{j} · G)]\}

= B + ∑_{i,j} a_{ij}E \{[u_{i} · G − \sqrt{\frac{π}{2}} · sign(u_{i} · G)] · [u_{j} · G − \sqrt{\frac{π}{2}} · sign(u_{j} · G)]\} ≥ B,

where here we have used the fact that A is positive semidefinite. The algorithm now simply chooses G at random, and computes x_{i} = y_{i} = sign(u_{i} · G).

We conclude this subsection with a sketch of (a modified version of) the argument of Grothendieck that shows that the integrality gap of (1) for the positive semidefinite case is indeed precisely π/2. We need the following Fact: If b and c are two random, independent, vectors on the unit sphere in R^{p}, then

E[(b · c)^{2}] = \frac{1}{p}  (8)

and

E[|b · c|] = (\sqrt{\frac{2}{π}} + o(1)) \frac{1}{\sqrt{p}},  (9)

where the o(1)-term tends to zero as p tends to infinity. Indeed, the computation of the first expectation is very simple; by rotation invariance we may assume that c = (1, 0, 0, …, 0) and then E[(b · c)^{2}] = E[b_{1}^{2}], where b = (b_{1}, b_{2}, …, b_{p}). However, by symmetry E[b_{1}^{2}] = \frac{1}{p}E[b_{1}^{2} +b_{2}^{2} +…+b_{p}^{2}] = \frac{1}{p}, implying (8). By the same reasoning, E[|b·c|] = E[|b_{1}|] which can now either be computed directly by integrating along the sphere, or can be estimated by noticing that it is well approximated by E[|\frac{g}{\sqrt{p}}|], where g is a standard Gaussian random variable. The simple computation for this case appears before the derivation of (6).

Armed with the above fact, we now define an n by n positive semidefinite matrix A = (a_{ij}) for which the ratio between the value of (1) and that of (2) is (nearly) π/2. Fix a large integer p, and let n be much larger. Let v_{1}, v_{2}, …, v_{n} be n independent random vectors chosen uniformly according to the normalized Haar measure on the unit sphere in R^{p}. Let A be the gram matrix of the vectors \frac{v_{i}}{n}, that is a_{ij} = \frac{1}{n^{2}} v_{i} · v_{j}. Obviously A is positive semidefinite. Moreover, if we substitute the unit vectors v_{i} in the program (2) we get

∑_{i,j} a_{ij}v_{i} · v_{j} = \frac{1}{n^{2}} ∑_{ij}(v_{i} · v_{j})^{2}.

When n tends to infinity, this converges to the average value of the square of the inner product between two random vectors on the unit sphere of R^{p}, which is, by (8), 1/p. Therefore, the optimal value of the program (2) for A is at least 1/p.

Consider, now, the optimal value of the integer program (1) for A. Let x_{i} ∈ {−1, 1} be a sign vector. Then

∑_{i,j} a_{ij}x_{i} · x_{j} = ∥\frac{1}{n} ∑_{i=1}^{n} x_{i}v_{i}∥^{2}.

Therefore, the value of the integer program is the square of the maximum possible norm of a vector \frac{1}{n} ∑_{i=1}^{n} x_{i}v_{i}, where x_{i} ∈ \{−1, 1\} for all i. If the direction of this optimal vector is given by the unit vector c, then, knowing c, it is clear how to choose x_{i} for each i; it simply has to be sign(v_{i} · c). With this choice of the signs x_{i}, the quantity

\frac{1}{n} ∑_{i=1}^{n} x_{i}v_{i} · c = ∥\frac{1}{n} ∑_{i=1}^{n} x_{i}v_{i}∥

converges, when n tends to infinity, to the average value of |v · c|, where v is a random vector on the sphere. By (9) this value is (\sqrt{2/π} + o(1))\frac{1}{\sqrt{p}}, where the o(1)-term tends to zero as p tends to infinity. Since n can be chosen to be arbitrarily large with respect to p, and as we do not have to consider all the infinitely many possible directions c, but can consider an appropriate ϵ-net of directions on the sphere, we conclude that if p is large and n is huge, then, with high probability, the value of the integer program (1) for A is at most

[(\sqrt{\frac{2}{π}} + o(1)) \frac{1}{\sqrt{p}}]^{2} = (\frac{2}{π} + o(1)) \frac{1}{p}.

It follows that the integrality gap is at least π/2, implying, by the discussion in the beginning of this subsection, that it is exactly π/2.

4.3 Constructing new vectors

Our approach in this subsection is based on a simplified version of Krivine’s proof, presented in [17], of Grothendieck’s Inequality, as described in [14]. We need the following simple lemma, which has already been mentioned briefly in the introduction, and which has been applied in Grothendieck’s original proof as well.

Lemma 4.1 (Grothendieck’s identity) For every two unit vectors u, v in a Hilbert space, if z is chosen randomly and uniformly according to the normalized Haar measure on the unit sphere of the space, then

\frac{π}{2} · E([sign (u · z)] · [sign (v · z)]) = arcsin (u · v) .

□

Using this lemma, we prove the following.

Lemma 4.2 For any set {u_{i} : 1 ≤ i ≤ n} ∪ {v_{j} : 1 ≤ j ≤ m} of unit vectors in a Hilbert space H, and for c = sinh^{−1}(1) = ln(1 + \sqrt{2}), there is a set \{u′_{i} : 1 ≤ i ≤ n\} ∪ \{v′_{j} : 1 ≤ j ≤ m\} of unit vectors in a Hilbert space H′, such that if z is chosen randomly and uniformly in the unit sphere of H′ then

\frac{π}{2} · E ([sign (u′_{i} · z)] · [sign (v′_{j} · z)]) = c u_{i} · v_{j}

for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.

Proof: Fix c as above, a Hilbert space H and u, v ∈ H. By Taylor’s expansion:

sin (c u · v) = ∑_{k=0}^{∞}(−1)^{k} \frac{c^{2k+1}}{(2k + 1)!} (u · v)^{2k+1} .

For every vector w and integer j denote by w^{⊗j} the j’th tensor power w ⊗ w ⊗ ⋯ ⊗ w (j terms). Then the above expansion becomes

sin (c u · v) = ∑_{k=0}^{∞}(−1)^{k} \frac{c^{2k+1}}{(2k + 1)!}u^{⊗(2k+1)} · v^{⊗(2k+1)}.

Consider the following vectors in the direct sum ⊕_{k=0}^{∞}H^{⊗(2k+1)}, whose k’th ”coordinate” is given by:

T (u)_{k} = (−1)^{k}\sqrt{\frac{c^{2k+1}}{(2k + 1)!}} · u^{⊗(2k+1)} and S(y)_{k} = \sqrt{\frac{c^{2k+1}}{(2k + 1)!}} · v^{⊗(2k+1)}

Then the above expansion boils down to sin (c u · v) = T (u) · S(v), or

c u · v = arcsin (T (u) · S(v)) .

Moreover,

∥T (u)∥^{2} = sinh (c · ∥u∥^{2}) and ∥S(v)∥^{2} = sinh (c · ∥v∥^{2}) .

Given the unit vectors u_{i}, v_{j}, recall that c = sinh^{−1}(1) and define u′_{i} = T (u_{i}) and v′_{j} = S(v_{i}). Note that all the vectors u′_{i}, v′_{j} are unit vectors (in the huge direct sum of tensor products we constructed). Let H′ be the span of u′_{i}, v′_{j}. It is an m + n-dimensional Hilbert space. Let z be a random vector chosen uniformly on its unit sphere. By Grothendieck’s identity (Lemma 4.1), for every i, j:

\frac{π}{2} · E([sign (T(u_{i}) · z)] · [sign (S(v_{j}) · z)]) = arcsin (T (u_{i}) · S(v_{j})) = c u_{i} · v_{j},

as needed. □

Theorem 4.3 There is a randomized polynomial time algorithm that given an input n by m matrix A = (a_{ij}) and unit vectors u_{i}, v_{j} in R^{n+m} finds x_{i}, y_{j} ∈ {−1, 1} such that the expected value of the sum ∑_{ij} a_{ij}x_{i}y_{j} is

\frac{2 ln(1 + \sqrt{2})}{π} ∑_{ij} a_{ij}u_{i} · v_{j}.

Therefore, there is a polynomial randomized ρ-approximation algorithm for computing ||A||_{∞↦1}, where ρ = ^{\frac{2 ln(1+\sqrt{2})}{π}} > 0.56.

Proof: By Lemma 4.2 there are vectors u′_{i}, v′_{j} satisfying the conclusion of the lemma. We can thus find such vectors in an m + n-dimensional space, using semidefinite programming. By linearity of expectation, with c = sinh^{−1}(1) as above,

c · ∑_{i,j} a_{ij}u_{i} · v_{j} = \frac{π}{2} · E(∑_{i,j} a_{ij} [sign (u′_{i} · z)] · [sign (v′_{j} · z)]).

We can now simply pick a random z and define x_{i} = sign(u′_{i} · z) and y_{j} = sign(v_{j} · z). □

4.4 The cut-norm

In this short subsection we observe that the same approximation ratio guaranteed in any approximation algorithm for ||A||_{∞↦1} can be obtained for the CUT NORM problem as well. Given an n by m matrix A = a_{ij}, augment it to an (n + 1) by (m + 1) matrix A′ = (a′_{ij}) by defining a′_{ij} = a_{ij} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m, a′_{i,m+1} = − ∑_{j=1}^{m} a_{ij} for all 1 ≤ i ≤ n, a′_{n+1,j} = − ∑_{i=1}^{n} a_{ij} for all 1 ≤ j ≤ m, and a′_{n+1,m+1} = 0. We claim that ||A′||_{C} = ||A||_{C}. Indeed, obviously ||A′||_{C} ≥ ||A||_{C}, as A is a submatrix of A′. Conversely, let I ⊂ {1, 2, …, n + 1}, J ⊂ {1, 2, , …, m + 1} satisfy ||A′||_{C} = | ∑_{i∈I,j∈J} a′_{ij}|. If n + 1 ∈ I replace it by its complement {1, 2, …, n + 1} \ I and similarly, if m + 1 ∈ J, replace it by its complement {1, 2, …, m + 1} \ J. As the sum of each row and the sum of each column of A′ is zero, the absolute value of the sum ∑_{i∈I,j∈J} a′_{ij} with the new sets I, J is still equal to ||A′||_{C}. This is, however, the sum of elements of a submatrix of A, implying that in fact ||A′||_{C} = ||A||_{C}, as claimed.

By the last part of Lemma 2.1, ||A′||_{∞↦1} = 4||A′||_{C}, and thus we can simply apply any algorithm for ρ-approximating ||A′||_{∞↦1} to obtain a similar ρ-approximation of ||A′||_{C} = ||A||_{C}.

5 Concluding remarks

• The Regularity Lemma of Szemerédi [24] is a result that asserts that any graph can be partitioned in a certain regular way. An algorithmic version of this lemma appears in [3], together with several algorithmic applications. The main step in the design of this algorithmic version, is an efficient procedure for approximating the ”regularity” of a pair of subsets in a given graph. This step can be improved using our results here. To state this improvement, we need a few definitions. Let G = (V, E) be an undirected graph, and let A, B be two disjoint nonempty subsets of V. Let e(A, B) denote the number of edges of G with an endpoint in A and an endpoint in B, and define the density of edges between A and B by d(A, B) = \frac{e(A,B)}{|A||B|}. For ϵ > 0, the pair (A, B) is called ϵ-regular if for every X ⊂ A and Y ⊂ B satisfying |X| ≥ ϵ|A| and |Y | ≥ ϵ|B|, the inequality

|d(A, B) − d(X, Y)| < ϵ

holds. The main step in [3] is a polynomial time algorithm that, given two disjoint subsets A, B ⊂ V in a graph G, where |A| = |B| = n, and given ϵ > 0, either decides that the pair (A, B) is ϵ-regular, or finds two subsets X ⊂ A and Y ⊂ B, each of size at least \frac{ϵ^{4}}{16}n, such that |d(A, B) − d(X, Y)| ≥ ϵ^{4}. A somewhat better result can be obtained using the approximation algorithms developed here. Given G = (V, E), ϵ > 0 and A, B as above, compute, first, the density d = d(A, B). Let F = (f_{ab})_{a∈A,b∈B} be the n by n matrix defined by f_{ab} = 1 − d if ab ∈ E and f_{ab} = −d if ab ∉ E. Note that if (A, B) is not ϵ-regular, then there are I ⊂ A, J ⊂ B satisfying |I| ≥ ϵn, |J| ≥ ϵn such that

| ∑_{a∈I,b∈J} f_{ab}| ≥ ϵ|I||J| ≥ ϵ^{3}n^{2},

that is, the cut-norm of F is at least ϵ^{3}n^{2}. Therefore, in this case our algorithm will find efficiently X ⊂ A, Y ⊂ B such that

| ∑_{a∈X,b∈Y} f_{ab}| ≥ 0.56ϵ^{3}n^{2}.

Obviously this implies, say, that |X| ≥ 0.5ϵ^{3}n, |Y | ≥ 0.5ϵ^{3}n and |d(X, Y) − d(A, B)| ≥ 0.5ϵ^{3}. If the algorithm does not find such sets, it can report that the pair (A, B) is ϵ-regular. This can be used instead of Corollary 3.3 in [3] to obtain efficiently a regular partition of any given graph with less parts than the ones ensured by the algorithm in [3] (but the number will still be huge; a tower of height polynomial in 1/ϵ, the degree of this polynomial will be smaller than the one in [3]).

• In [7] Frieze and Kannan describe an efficient algorithm for finding what they call a cutdecomposition of a given n by m real matrix A, and apply it to obtain efficient approximation algorithms for various dense graph and matrix problems.

Consider matrices with a set of rows indexed by R and a set of columns indexed by S. For I ⊂ R and J ⊂ S, and for a real d, the cut matrix D = CUT (I, J, d) is the matrix (d_{ij})_{i∈R,j∈S} defined by d_{ij} = d if i ∈ I, j ∈ J and d_{ij} = 0 otherwise. A cut-decomposition of A expresses it in the form

A = D^{(1)} + … + D^{(s)} + W,

where the matrices D^{(i)} are cut matrices, and the matrix W = (w_{kl}) has a relatively small cut-norm. The authors of [7] describe an efficient algorithm that produces, for any given n by m matrix A with entries in [−1, 1], a cut-decomposition in which the number of cut matrices is O(1/ϵ^{2}), and the cut-norm of the matrix W is at most ϵnm. This is done as follows. Starting with W^{(0)} = A, suppose that the first i cut matrices D^{(1)}, …, D^{(i)} have already been defined, and consider the difference W^{(i)} = A − ∑_{j=1}^{i} D^{(j)}. If the cut-norm of this difference is already smaller than ϵnm, we are done. Otherwise, let I, J be sets of rows and columns such that

| ∑_{k∈I,l∈J} w_{kl}^{(i)}| ≥ ρϵnm,  (10)

where ρ > 0 is an absolute positive constant. Let d be the average value of the entries w_{kl}^{(i)} for k ∈ I, l ∈ J, and define D^{(i+1)} = CUT (I, J, d), W^{(i+1)} = W^{(i)} − D^{(i+1)}. A simple computation, described in [7], shows that the sum of squares of the entries of the new matrix W^{(i+1)} is at most the sum of squares of the entries of the matrix W^{(i)} minus ρ^{2}ϵ^{2}nm. Therefore, this process must terminate after at most \frac{1}{ρ^{2}ϵ^{2}} steps. The main step in the algorithm is clearly that of finding the sets I, J that satisfy (10), and the authors are able to do it efficiently only when the cut-norm is at least a constant fraction of nm. Our algorithm here enables us to perform this task efficiently (even if ϵ is, say, 1/n^{0.001}, which is not feasible using the approach of [7], as the running time of their algorithm is exponential in 1/ϵ^{2}).

• The rounding techniques described in Section 3 or in Subsection 4.1 (but not the one described in Subsection 4.3) can be used to find efficiently, for any given square n by n matrix A = (a_{ij}), a vector (x_{1}, …, x_{n}) ∈ {−1, 1}, such that the value of | ∑_{ij} a_{ij}x_{i}x_{j}| is at least a ρ-fraction of the maximum possible value of this quantity (or even the quantity | ∑_{ij} a_{ij}u_{i} · u_{j}|, where u_{i}, u_{j} are unit vectors in a Hilbert space.) Note that here we do not assume that A is positive semidefinite (but we try to maximize the absolute value of the quadratic form, not the quadratic form itself). By applying this approximation algorithm to a matrix defined from a graph G as in the first comment of this section, we can find an induced subgraph that approximates the maximum possible deviation of the total number of edges from its expected value among all induced subgraphs of the graph.

• There is a lot known on the complex version of Grothendieck’s Inequality [12, 16], and it may be interesting to find algorithmic or combinatorial applications of these results.

• We believe that the method described in this paper will find further applications, as it provides a rounding technique that can, at least in the cases considered here, handle cancellations between positive and negative terms.

• It will be interesting to improve the approximation guarantee of our algorithms. It will also be interesting to find a ρ-approximation algorithm for the CUT NORM problem (for any absolute positive constant ρ) which does not apply semidefinite programming and/or can be analyzed without relying on Grothendieck’s Inequality.

Acknowledgment: Part of this work was carried out during a visit of the first author at Microsoft Research, Redmond, WA, and he thanks his hosts at Microsoft for their hospitality.

References

[1] N. Alon, L. Babai and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms 7(1986), 567-583.

[2] N. Alon, W. F. de la Vega, R. Kannan and M. Karpinski, Random sampling and approximation of MAX-CSP problems, Proc. of the 34^{th} ACM STOC, ACM Press (2002), 232–239.

[3] N. Alon, R. A. Duke, H. Lefmann, V. Rödl and R. Yuster, The algorithmic aspects of the Regularity Lemma, Proc. 33^{rd} IEEE FOCS, Pittsburgh, IEEE (1992), 473-481. Also: J. of Algorithms 16 (1994), 80-109.

[4] N. Alon, Y. Matias and M. Szegedy, The space complexity of approximating the frequency moments, Proc. of the 28^{th} ACM STOC, ACM Press (1996), 20-29. Also; J. Comp. Sys. Sci. 58 (1999), 137-147.

[5] N. Alon and J. Spencer, The Probabilistic Method, Second Edition, Wiley, New York, 2000.

[6] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and intractability of approximation problems, Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, 1992, 14–23.

[7] A. M. Frieze and R. Kannan, Quick Approximation to matrices and applications, Combinatorica 19 (2) (1999) pp 175–200.

[8] U. Feige and M. Langberg, The RPR^{2} Rounding Technique for Semidefinite Programs, Proceedings of the 28th International Colloquium on Automata, Languages and Programming, Crete, Greece, 2001, 213–224.

[9] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169–197.

[10] A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques, Bol. Soc. Mat. Sao Paulo 8 (1953), 1–79.

[11] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995), 1115–1145.

[12] U. Haagerup, A new upper bound for the complex Grothendieck constant, Israel Journ. Math. 60 (1987), 199–224.

[13] J. Håstad, Some optimal inapproximability results, J. ACM 48 (2001), 798–859.

[14] G. J. O. Jameson, Summing and nuclear norms in Banach space theory, London Mathematical Society Student Texts, 8, Cambridge University Press, Cambridge, 1987.

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

[16] H. König, On the complex Grothendieck constant in the n-dimensional case, London Math. Soc. Lect. Notes 158 (1990), 181–198.

[17] J. L. Krivine, Sur la constante de Grothendieck, C. R. Acad. Sci. Paris Ser. A-B 284 (1977), 445–446.

[18] M. Lewin, D. Livnat and U. Zwick, Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems, Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization, Cambridge, Massachusetts, 2002, 67–82.

[19] J. Lindenstrauss and A. Pełczyński, Absolutely summing operators in L_{p}-spaces and their applications, Studia Math. 29 (1968), 275-326.

[20] S. Mahajan and H. Ramesh, Derandomizing approximation algorithms based on semidefinite programming, SIAM J. Comput. 28 (1999), 1641–1663.

[21] Y. E. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software 9 (1998), 141–160.

[22] C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comp. Sys. Sci. 43 (1991), 425–440.

[23] R. E. Rietz, A proof of the Grothendieck inequality, Israel J. Math. 19 (1974), 271–276.

[24] E. Szemerédi, Regular partitions of graphs, in: Proc. Colloque Inter. CNRS (J. -C. Bermond, J. -C. Fournier, M. Las Vergnas and D. Sotteau eds.), 1978, 399-401.

[25] U. Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the 31th Annual ACM Symposium on Theory of Computing (STOC), Atlanta, Georgia, 1999, 679–687.