Authors Jop Bri{\"e}t, Fernando M{\'a}rio {de} Oliveira Filho, Frank Vallentin,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105
www.theoryofcomputing.org
Grothendieck Inequalities for
Semidefinite Programs with Rank Constraint
Jop Briët∗ Fernando Mário de Oliveira Filho† Frank Vallentin‡
Received May 4, 2012; Revised January 21, 2014; Published May 31, 2014
Abstract: Grothendieck inequalities are fundamental inequalities which are frequently
used in many areas of mathematics and computer science. They can be interpreted as upper
bounds for the integrality gap between two optimization problems: a difficult semidefinite
program with rank-1 constraint and its easy semidefinite relaxation where the rank constraint
is dropped. For instance, the integrality gap of the Goemans-Williamson approximation
algorithm for MAX CUT can be seen as a Grothendieck inequality. In this paper we
consider Grothendieck inequalities for ranks greater than 1 and we give two applications:
approximating ground states in the n-vector model in statistical mechanics and XOR games
in quantum information theory.
ACM Classification: G.1.6, G.2.2
AMS Classification: 68W25, 90C22
Key words and phrases: randomized rounding, Grothendieck inequality, n-vector model, XOR games
1 Introduction
Let G = (V, E) be a graph with finite vertex set V and edge set E ⊆ V2 . Let A : V ×V → R be a symmetric
matrix whose rows and columns are indexed by the vertex set of G, and r be a positive integer. The
∗ Supported by Vici grant 639.023.302 from the Netherlands Organization for Scientific Research (NWO), by the European
Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848,
by the Dutch BSIK/BRICKS project and by the European grant QCS.
† Supported by NWO Rubicon grant 680-50-1014.
‡ Supported by Vidi grant 639.032.917 from the Netherlands Organization for Scientific Research (NWO).
© 2014 Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2014.v010a004
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
graphical Grothendieck problem with rank-r constraint is the following optimization problem:
r−1
SDPr (G, A) = max ∑ A(u, v) f (u) · f (v) : f : V → S ,
{u,v}∈E
where Sr−1 = { x ∈ Rr : x · x = 1 } is the (r − 1)-dimensional unit sphere. The rank-r Grothendieck
constant of the graph G is the smallest constant K(r, G) so that for all symmetric matrices A : V ×V → R
the following inequality holds:
SDP∞ (G, A) ≤ K(r, G) SDPr (G, A) . (1.1)
Here S∞ denotes the unit sphere of the Hilbert space l 2 (R) of square summable sequences, which contains
Rn as the subspace of the first n components. It is easy to see that K(r, G) ≥ 1. In this paper, we prove
new upper bounds for K(r, G).
1.1 Some history
Inequality (1.1) is called a Grothendieck inequality because it first appeared in the work [23] of
Grothendieck on the metric theory of tensor products. More precisely, Grothendieck considered the case
r = 1 for bipartite graphs, although in quite a different language. Grothendieck proved that in this case
K(1, G) is upper bounded by a constant that is independent of the size of G.
Later, Lindenstrauss and Pełczyński [34] reformulated Grothendieck’s inequality for bipartite graphs
in a way that is very close to the formulation we gave above. The graphical Grothendieck problem
with rank-1 constraint was introduced by Alon, Makarychev, Makarychev, and Naor [3]. Haagerup [24]
considered the complex case of Grothendieck’s inequality; his upper bound is also valid for the real case
r = 2. The higher rank case for bipartite graphs was introduced by Briët, Buhrman, and Toner [11].
1.2 Computational perspective
There has been a recent surge of interest in Grothendieck inequalities by the computer science community.
The problem SDPr (G, A) is a semidefinite maximization problem with rank-r constraint:
SDPr (G, A) = max ∑ A(u, v)X(u, v) : X ∈ RV0×V ,
{u,v}∈E
X(u, u) = 1 for all u ∈ V ,
rank X ≤ r ,
where RV0×V is the set of matrices X : V ×V → R that are positive semidefinite.
On the one hand, SDPr (G, A) is generally a difficult computational problem. For instance, if r = 1
and G is the complete bipartite graph Kn,n on 2n nodes, and if A is the Laplacian matrix of a graph G0
on n nodes, then computing SDP1 (Kn,n , A) is equivalent to computing the weight of a maximum cut of
G0 . The maximum cut problem (MAX CUT) is one of Karp’s 21 NP-complete problems. On the other
hand, if we relax the rank-r constraint, then we deal with SDP∞ (G, A), which is an easy computational
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 78
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
problem: Obviously, one has SDP∞ (G, A) = SDP|V | (G, A) and computing SDP|V | (G, A) amounts to
solving a semidefinite programming problem (see, e. g., Vandenberghe, Boyd [47]). Therefore one may
approximate it to any fixed precision in polynomial time by using the ellipsoid method or interior point
algorithms.
In many cases the optimal constant K(r, G) is not known and so one is interested in finding upper
bounds for K(r, G). Usually, proving an upper bound amounts to giving a randomized polynomial-
time approximation algorithm for SDPr (G, A). In the case of the MAX CUT problem, Goemans and
Williamson [22] pioneered an approach based on randomized rounding: One rounds an optimal solution
of SDP∞ (G, A) to a feasible solution of SDPr (G, A). The expected value of the rounded solution is then
related to the one of the original solution, and this gives an upper bound for K(r, G). Using this basic
idea, Goemans and Williamson [22] showed that for any matrix A : V ×V → R that is a Laplacian matrix
of a weighted graph with nonnegative edge weights one has
SDP∞ (Kn,n , A) ≤ (0.878 . . . )−1 SDP1 (Kn,n , A) .
1.3 Applications and references
Grothendieck’s inequality is a fundamental inequality in the theory of Banach spaces. Many books on
the geometry of Banach spaces contain a substantial treatment of the result. We refer for instance to the
books by Pisier [41], Jameson [26], and Garling [21].
During the last years, especially after Alon and Naor [4] pointed out the connection between the
inequality and approximation algorithms using semidefinite programs, Grothendieck’s inequality has also
become a unifying and fundamental tool outside of functional analysis.
It has applications in optimization (Nesterov [40], Nemirovski, Roos, Terlaky [39], Megretski [37]),
extremal combinatorics (Alon, Naor [4]), system theory (Ben-Tal, Nemirovski [9]), machine learn-
ing (Charikar, Wirth [14], Khot, Naor [28, 29]), communication complexity (Linial, Shraibman [35]),
quantum information theory (Tsirel’son [46], Regev, Toner [44]), and computational complexity (Khot,
O’Donnell [30], Arora, Berger, Kindler, Safra, Hazan [6], Khot and Naor [27], Raghavendra, Steurer [42]).
The references above mainly deal with the combinatorial rank r = 1 case, when S0 = {−1, +1}. For
applications in quantum information (Briët, Buhrman, Toner [11]) and in statistical mechanics (mentioned
in Alon, Makarychev, Makarychev, Naor [3], Kindler, Naor, Schechtman [31]) the more geometrical case
when r > 1 is of interest—this case is the subject of this paper.
In statistical mechanics, the problem of computing SDPn (G, A) is known as finding ground-states of
the n-vector model. Introduced by Stanley [45], the n-vector model1 describes the interaction of particles
in a spin glass with ferromagnetic and anti-ferromagnetic interactions.
Let G = (V, E) be the interaction graph where the vertices are particles and where edges indicate
which particles interact. The potential function A : V ×V → R is 0 if u and v are not adjacent, it is positive
if there is ferromagnetic interaction between u and v, and it is negative if there is anti-ferromagnetic
interaction. The particles possess a vector-valued spin f : V → Sn−1 . In the absence of an external field,
1 The case n = 1 is known as the Ising model, the case n = 2 as the XY model, the case n = 3 as the Heisenberg model, and
the case n = ∞ as the Berlin-Kac spherical model.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 79
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
the total energy of the system is given by the Hamiltonian
H( f ) = − ∑ A(u, v) f (u) · f (v) .
{u,v}∈E
The ground state of this model is a configuration of spins f : V → Sn−1 which minimizes the total energy,
so finding the ground state is the same as solving SDPn (G, A). Typically, the interaction graph has small
chromatic number, e. g., the most common case is when G is a finite subgraph of the integer lattice Zn
where the vertices are the lattice points and where two vertices are connected if their Euclidean distance
is one. These graphs are bipartite since they can be partitioned into even and odd vertices, corresponding
to the parity of the sum of the coordinates.
We also briefly describe the connection to quantum information theory. In an influential paper,
Einstein, Podolsky, and Rosen [18] pointed out an anomaly of quantum mechanics that allows spatially
separated parties to establish peculiar correlations by each performing measurements on a private quantum
system: entanglement. Later, Bell [8] proved that local measurements on a pair of spatially separated,
entangled quantum systems, can give rise to joint probability distributions of measurement outcomes
that violate certain inequalities (now called Bell inequalities), satisfied by any classical distribution.
Experimental results of Aspect, Grangier, and Roger [7] give strong evidence that nature indeed allows
distant physical systems to be correlated in such non-classical ways.
XOR games, first formalized by Cleve, Høyer, Toner, and Watrous [15], constitute the simplest model
in which entanglement can be studied quantitatively. In an XOR game, two players, Alice and Bob,
receive questions u and v (resp.) that are picked by a referee according to some probability distribution
π(u, v) known to everybody in advance. Without sharing their questions, the players have to answer the
referee with bits a and b (resp.), and win the game if and only if the exclusive-OR of their answers a ⊕ b
equals the value of a Boolean function g(u, v); the function g is also known in advance to all three parties.
In a quantum-mechanical setting, the players determine their answers by performing measurements
on their shares of a pair of entangled quantum systems. A state of a pair of d-dimensional quantum
2 2
systems is a trace-1 positive semidefinite operator ρ ∈ Cd0×d . The systems are entangled if ρ cannot
be written as a convex combination of tensor products of d-by-d positive semidefinite matrices. For
each question u, Alice has a two-outcome measurement defined by a pair of d-by-d positive semidefinite
matrices {A0u , A1u } that satisfies A0u + A1u = I, where I is the identity matrix. Bob has a similar pair {B0v , B1v }
for each question v. When the players perform their measurements, the probability that they obtain bits a
and b is given by Tr(Aau ⊗ Bbv ρ).
The case d = 1 corresponds
to a classical setting. In this case, the maximum winning probability
equals 1 + SDP1 (G, A) /2, where G is the complete bipartite graph with Alice and Bob’s questions
on opposite sides of the partition, and A(u, v) = (−1)g(u,v) π(u, v)/2 for pairs {u, v} ∈ E and A(u, v) = 0
everywhere else.
Tsirel’son [46] related the maximum winning probability ωd∗ (π, g) of the game (π, g), when the
players are restricted to measurements on d-dimensional quantum systems, to the quantity SDPr (G, A).
In particular, he proved that
1 + SDPblog dc (G, A) 1 + SDP2d (G, A)
≤ ωd∗ (π, g) ≤ .
2 2
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 80
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
The quantity SDPr (G, A) thus gives bounds on the maximum winning probability of XOR games when
players are limited in the amount of entanglement they are allowed to use. The rank-r Grothendieck
constant K(r, G) of the bipartite graph G described above gives a quantitative bound on the advantage
that unbounded entanglement gives over finite entanglement in XOR games.
1.4 Our results and methods
The purpose of this paper is to prove explicit upper bounds for K(r, G). We are especially interested in
the case of small r and graphs with small chromatic number, although our methods are not restricted to
this. Our main theorem, Theorem 1.2, which will be stated shortly, can be used to compute the bounds
for K(r, G) shown in Table 1 below.
r bipartite G tripartite G
1 1.782213 . . . 3.264251 . . .
2 1.404909 . . . 2.621596 . . .
3 1.280812 . . . 2.412700 . . .
4 1.216786 . . . 2.309224 . . .
5 1.177179 . . . 2.247399 . . .
6 1.150060 . . . 2.206258 . . .
7 1.130249 . . . 2.176891 . . .
8 1.115110 . . . 2.154868 . . .
9 1.103150 . . . 2.137736 . . .
10 1.093456 . . . 2.124024 . . .
Table 1: Bounds on Grothendieck’s constant.
Theorem 1.2 actually gives, for every r, a randomized polynomial-time approximation algorithm
for the optimization problem SDPr (G, A). So in particular it provides a randomized polynomial-time
approximation algorithm for computing the ground states of the 3-vector model, also known as the
Heisenberg model, in the lattice Z3 with approximation ratio 0.78 . . . = (1.28 . . .)−1 . This result can be
regarded as one of the main contributions of this paper.
To prove the main theorem we use the framework of Krivine and Haagerup which we explain below.
Our main technical contributions are a matrix version of Grothendieck’s identity (Lemma 2.1) and a
method to construct new unit vectors which can also deal with nonbipartite graphs (Lemma 4.1).
The strategy of Haagerup and Krivine is based on the following embedding lemma:
Lemma 1.1. Let G = (V, E) be a graph and choose Z = (Zi j ) ∈ Rr×|V | at random so that each entry
is distributed independently according to the normal distribution with mean 0 and variance 1, that is,
Zi j ∼ N(0, 1).
Given f : V → S|V |−1 , there is a function g : V → S|V |−1 such that whenever u and v are adjacent in
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 81
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
G, then
Zg(u) Zg(v)
E · = β (r, G) f (u) · f (v)
kZg(u)k kZg(v)k
for some constant β (r, G) depending only on r and G.
In the statement above we are vague regarding the constant β (r, G). We will soon define more
precisely the constant β (r, G), and in Section 4 we will provide a precise statement of this lemma
(cf. Lemma 4.1 there). Right now this precise statement is not relevant to our discussion.
Now, the strategy of Haagerup and Krivine amounts to analyzing the following four-step procedure
that yields a randomized polynomial-time approximation algorithm for SDPr (G, A):
Algorithm A. Takes as input a finite graph G = (V, E) with at least one edge and a symmetric matrix
A : V ×V → R, and returns a feasible solution h : V → Sr−1 of SDPr (G, A).
1. Solve SDP∞ (G, A), obtaining an optimal solution f : V → S|V |−1 .
2. Use f to construct g : V → S|V |−1 according to Lemma 1.1.
3. Choose Z = (Zi j ) ∈ Rr×|V | at random so that every matrix entry Zi j is distributed independently
according to the standard normal distribution with mean 0 and variance 1, that is, Zi j ∼ N(0, 1).
4. Define h : V → Sr−1 by setting h(u) = Zg(u)/kZg(u)k.
To analyze this procedure, we compute the expected value of the feasible solution h. Using Lemma 1.1
we obtain
SDPr (G, A) ≥ E ∑ A(u, v)h(u) · h(v)
{u,v}∈E
= ∑ A(u, v)E[h(u) · h(v)]
{u,v}∈E (1.2)
= β (r, G) ∑ A(u, v) f (u) · f (v)
{u,v}∈E
= β (r, G) SDP∞ (G, A) ,
and so we have K(r, G) ≤ β (r, G)−1 .
If we were to skip step (2) and apply step (4) to f directly, then the expectation E[h(u) · h(v)] would
be a non-linear function of f (u) · f (v), which would make it difficult to assess the quality of the feasible
solution h. The purpose of step (2) is to linearize this expectation, which allows us to estimate the quality
of h in terms of a linear function of SDPr (G, A).
The constant β (r, G) in Lemma 1.1 is defined in terms of the Taylor expansion of the inverse of the
function Er : [−1, 1] → [−1, 1] given by
Zx Zy
Er (x · y) = E · ,
kZxk kZyk
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 82
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
where x, y ∈ S∞ and Z = (Zi j ) ∈ Rr×∞ is chosen so that its entries are independently distributed according
to the normal distribution with mean 0 and variance 1. The function Er is well-defined since the
expectation above is invariant under orthogonal transformations.
The function Er−1 has the Taylor expansion
∞
Er−1 (t) = ∑ b2k+1t 2k+1 ,
k=0
with a positive radius of convergence around zero, as will be shown in Section 3. Our main theorem can
be thus stated:
Theorem 1.2. The Grothendieck constant K(r, G) is at most β (r, G)−1 where the number β (r, G) is
defined by the equation
∞
1
∑ |b2k+1 |β (r, G)2k+1 = ϑ (G) − 1 , (1.3)
k=0
where b2k+1 are the coefficients of the Taylor expansion of Er−1 and where ϑ (G) is the theta number of
the complement of the graph G. (In particular, there exists a number satisfying (1.3).)
(For a definition of the Lovász theta number of a graph, see (4.1) in Section 4.)
The Taylor expansion of Er is computed in Section 2 and the Taylor expansion of Er−1 is treated in
Section 3. A precise version of Lemma 1.1 is stated and proved in Section 4, following Krivine [33]. As
we showed above, this lemma, together with Algorithm A, then implies Theorem 1.2. In Section 6 we
discuss how we computed Table 1. We computed the entries numerically and we strongly believe that all
digits are correct even though we do not have a formal mathematical proof.
We finish this section with some remarks. When r = 1 and G is bipartite, Theorem 1.2 specializes
to Krivine’s [33] bound for the original Grothendieck constant KG = limn→∞ K(1, Kn,n ). For more than
thirty years this was the best known upper bound, and it was conjectured by many to be optimal. However,
shortly after our work appeared in preprint form, Braverman, Makarychev, Makarychev and Naor [10]
showed that Krivine’s bound can be slightly improved. In this light we now believe that the upper bound
in Theorem 1.2 is not tight.
The best known lower bound on KG is 1.676956 . . ., due to Davie [16] and Reeds [43] (see also Khot
and O’Donnell [30]).
When r = 2 and G is bipartite, Theorem 1.2 specializes to Haagerup’s [24] upper bound for the
complex Grothendieck constant KGC ; this is currently the best known upper bound for this constant.
Using different techniques, in [13] we proved for the asymptotic regime where r is large that
K(r, Kn,n ) = 1 + Θ(1/r) holds. A recent argument of Naor and Regev [38] (which was used to show
that specific variations of Algorithm A exist whose approximation quality become arbitrary close to the
Grothendieck constant) implies that Theorem 1.2 can also be used to prove an upper bound of 1 + O(1/r).
For graphs with large chromatic number Alon, Makarychev, Makarychev, and Naor [3] give the best
known bounds for K(1, G). They prove a logarithmic dependence on the chromatic number of the graph
(actually on the theta number of the complement of G, cf. Section 4) whereas our methods only give a
linear dependence. Although our main focus is on small chromatic numbers, for completeness we extend
the results of [3] for large chromatic numbers to r ≥ 2 in Section 5.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 83
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
2 A matrix version of Grothendieck’s identity
In the analysis of many approximation algorithms that use semidefinite programming the following
identity plays a central role: Let u, v be unit (column) vectors in Rn and let Z ∈ R1×n be a random (row)
vector whose entries are distributed independently according to the standard normal distribution with
mean 0 and variance 1. Then,
Zu Zv 2
E[sign(Zu) sign(Zv)] = E · = arcsin(u · v) .
kZuk kZvk π
For instance, the celebrated algorithm of Goemans and Williamson [22] for approximating the MAX
CUT problem is based on this. The identity is called Grothendieck’s identity since it appeared for the first
time in Grothendieck’s work on the metric theory of tensor products [23, Proposition 4, p. 63] (see also
Diestel, Fourie, and Swart [17]).
In this section we extend Grothendieck’s identity from vectors to matrices by replacing the arcsine
function by a hypergeometric function, defined as follows. For any nonnegative integers p, q, real numbers
a1 , a2 , . . . , a p and strictly positive real numbers b1 , b2 , . . . , bq , there is a hypergeometric function
(a1 )k (a2 )k · · · (a p )k xk
∞
a1 , a2 , . . . , a p
F
p q ; x = ∑ ,
b1 , b2 , . . . , bq k=0 (b1 )k (b2 )k · · · (bq )k k!
where
(c)k = c(c + 1)(c + 2) · · · (c + k − 1)
denotes the rising factorial function. Conforming with the notation of Andrews, Askey and Roy [5], if
p = 0 we substitute the absent parameters ai by a horizontal line:
0 Fq ;x .
b1 , b2 , . . . , bq
Lemma 2.1. Let u, v be unit vectors in Rn and let Z ∈ Rr×n be a random matrix whose entries are
distributed independently according to the standard normal distribution with mean 0 and variance 1.
Then,
2 Γ((r + 1)/2) 2
Zu Zv 1/2, 1/2 2
E · = (u · v) 2 F1 ; (u · v)
kZuk kZvk r Γ(r/2) r/2 + 1
(2.1)
2 Γ((r + 1)/2) 2 ∞ (1/2)k (1/2)k (u · v)2k+1
= ∑ .
r Γ(r/2) k=0 (r/2 + 1)k k!
Before proving the lemma we review special cases known in the literature. If r = 1, then we get the
original Grothendieck’s identity:
2
E[sign(Zu) sign(Zv)] = arcsin(u · v)
π
1 (u · v)3 1 · 3 (u · v)5
2
= u·v+ + +··· .
π 2 3 2·4 5
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 84
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
The case r = 2 is due to Haagerup [24]:
Zu Zv 1
E(u · v) − (1 − (u · v)2 )K(u · v)
E · =
kZuk kZvk u·v
2 !
1 (u · v)3 1 · 3 2 (u · v)5
π
= u·v+ + +··· ,
4 2 2 2·4 3
where K and E are the complete elliptic integrals of the first and second kind. Note that on page 201 of
Haagerup [24] π/2 has to be π/4. Briët, Oliveira, and Vallentin [12] computed, for every r, the zeroth
coefficient of the series in (2.1), which is the Taylor series of the expectation.
The following elegant proof of Grothendieck’s identity has become a classic: We have
sign(Zu) sign(Zv) = 1
if and only if the vectors u and v lie on the same side of the hyperplane orthogonal to the vector Z ∈ R1×n .
Now we project this n-dimensional situation to the plane spanned by u and v. Then the projected
random hyperplane becomes a random line. This random line is distributed according to the uniform
probability measure on the unit circle because Z is normally distributed. Now one obtains the final result
by measuring intervals on the unit circle: The probability that u and v lie on the same side of the line is
1 − arccos(u · v)/π.
We do not have such a picture proof for our matrix version. Our proof is based on the rotational
invariance of the normal distribution and integration with respect to spherical coordinates together with
some identities for hypergeometric functions. A similar calculation was done by König and Tomczak-
Jaegermann [32]. It would be interesting to find a more geometrical proof of the lemma.
For computing the first coefficient of the Taylor series in [12] we took a slightly different route: We
integrated using the Wishart distribution of 2 × 2-matrices.
Proof of Lemma 2.1. Let Zi ∈ Rn be the i-th row of the matrix Z, with i = 1, . . . r. We define vectors
Z1 · u Z1 · v
Z2 · u Z2 · v
x= . and y= .
. . .
.
Zr · u Zr · v
so that we have x · y = (Zu) · (Zv). Since the probability distribution of the vectors
√ Zi is invariant under
orthogonal transformations we may assume that u = (1, 0, . . . , 0) and v = (t, 1 − t 2 , 0, . . . , 0) and so the
pair (x, y) ∈ Rr × Rr is distributed according to the probability density function (see, e. g., Feller [20,
p. 69])
p
2 −r x · x − 2tx · y + y · y
(2π 1 − t ) exp − .
2(1 − t 2 )
Hence,
x y x y x · x − 2tx · y + y · y
p Z Z
2 −r
E · = (2π 1 − t ) · exp − dx dy .
kxk kyk Rr Rr kxk kyk 2(1 − t 2 )
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 85
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
By using spherical coordinates x = αξ , y = β η, where α, β ∈ [0, ∞) and ξ , η ∈ Sr−1 , we rewrite the
above integral as
α2 + β 2
Z Z
αβtξ · η
Z ∞Z ∞
r−1
(αβ ) exp − ξ · η exp dω(ξ ) dω(η) dα dβ ,
0 0 2(1 − t 2 ) Sr−1 Sr−1 1 − t2
where ω is the surface-area measure, such that ω(Sn−1 ) = 2π n/2 /Γ(n/2).
If r = 1, we get for the inner double integral
αβtξ · η
Z Z
αβt
ξ · η exp dω(ξ ) dω(η) = 4 sinh
S0 S0 1 − t2 1 − t2
2 !
αβt αβt
=4 0 F1 ; .
1 − t2 3/2 2(1 − t 2 )
Now we consider the case when r ≥ 2. Since the inner double integral over the spheres only depends
on the inner product p = ξ · η it can be rewritten as
Z 1
αβt p
ω(S r−2
)ω(S r−1
) p exp (1 − p2 )(r−3)/2 d p ,
−1 1 − t2
where
4π r−1/2
ω(Sr−2 )ω(Sr−1 ) = .
Γ(r/2)Γ((r − 1)/2)
Integration by parts yields
Z 1
αβt p
p(1 − p2 )(r−3)/2 exp dp
−1 1 − t2
Z 1
αβt 2 (r−1)/2 αβt p
= (1 − p ) exp dp.
(r − 1)(1 − t 2 ) −1 1 − t2
The last integral can be rewritten using the modified Bessel function of the first kind (cf. Andrews, Askey,
Roy [5, p. 235, Exercise 9])
Z 1
2 (r−1)/2αβt p
(1 − p ) exp dp
−1 1 − t2
r/2
√ 2(1 − t 2 )
αβt
= Γ((r + 1)/2) π Ir/2 .
αβt 1 − t2
One can write Ir/2 as a hypergeometric function (cf. Andrews, Askey, and Roy [5, (4.12.2)])
(x/2)2k (x/2)r/2
∞ x 2
r/2
Ir/2 (x) = (x/2) ∑ = 0 F1 ; .
k=0 k!Γ(r/2 + k + 1) Γ((r + 2)/2) (r + 2)/2 2
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 86
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
Putting things together, we get
Z 1
αβt p
r−2
ω(S )ω(S ) r−1
p exp (1 − p2 )(r−3)/2 d p
−1 1 − t2
2 !
4π r
αβt αβt
= 0 F1 ; .
Γ(r/2)2 r 1 − t 2 (r + 2)/2 2(1 − t 2 )
Notice that the last formula also holds for r = 1. So we can continue without case distinction.
Now we evaluate the outer double integral
2 !
α2 + β 2
Z ∞Z ∞
r αβt
(αβ ) exp − 0 F1 ; dα dβ .
0 0 2(1 − t 2 ) (r + 2)/2 2(1 − t 2 )
Here the inner integral equals
2 !
α2
Z ∞
r αβt
α exp − 0 F1 ; dα ,
0 2(1 − t 2 ) (r + 2)/2 2(1 − t 2 )
and doing the substitution γ = α 2 /(2(1 − t 2 )) gives
γ(βt)2
Z ∞
(r−1)/2 2 (r+1)/2 (r−1)/2
2 (1 − t ) γ exp(−γ) 0 F1 ; dγ ,
0 (r + 2)/2 2(1 − t 2 )
which is by the Bateman Manuscript Project [19, p. 337 (11)] equal to
(βt)2
(r−1)/2 2 (r+1)/2 (r + 1)/2
2 (1 − t ) Γ((r + 1)/2)1 F1 ; .
(r + 2)/2 2(1 − t 2 )
Now we treat the remaining outer integral in a similar way, using [19, p. 219 (17)], and get that
β2 (βt)2
Z ∞
r (r + 1)/2
β exp − 1 F1 ; dβ
0 2(1 − t 2 ) (r + 2)/2 2(1 − t 2 )
(r−1)/2 2 (r+1)/2 (r + 1)/2, (r + 1)/2 2
=2 (1 − t ) Γ((r + 1)/2)2 F1 ;t .
(r + 2)/2
By applying Euler’s transformation (cf. Andrews, Askey, and Roy [5, (2.2.7)])
(r + 1)/2, (r + 1)/2 2 2 −r/2 1/2, 1/2 2
2 F1 ;t = (1 − t ) 2 F1 ;t
(r + 2)/2 (r + 2)/2
and after collecting the remaining factors we arrive at the result.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 87
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
3 Convergence radius
To construct the new vectors in the second step of Algorithm A we will make use of the Taylor series
expansion of the inverse of Er . Locally around zero we can expand the function Er−1 as
∞
Er−1 (t) = ∑ b2k+1t 2k+1 , (3.1)
k=0
but in the proof of Lemma 4.1 it will be essential that this expansion be valid on [−β (r, G), β (r, G)]. In
the case r = 1 we have E1−1 (t) = sin((π/2)t), whose Taylor expansion has infinite convergence radius.
In this section we show that for all r ≥ 2 the convergence radius of the Taylor series of Er−1 is also large
enough for our purposes. The case r = 2 was previously dealt with by Haagerup [24], who proved that
the convergence radius is at least 1. Our proof, which applies uniformly for all cases r ≥ 2 (but gives a
smaller radius for r = 2), is based on elementary techniques from complex analysis.
Let D = { z ∈ C : |z| < 1 } denote the open unit disc and for a real number c > 0 define cD = { z ∈
C : |z| < c }. Since the function Er can be represented by a Taylor series in [−1, 1], it has an analytic
extension Er in D given by
!2
1/2, 1/2 2 2 Γ (r + 1)/2
Er (z) = Cr z 2 F1 ;z , Cr = . (3.2)
r/2 + 1 r Γ(r/2)
Theorem 3.1. Let r be a positive integer. Then, the Taylor series (3.1) has convergence radius at least
|Er (i)|.
Theorem 3.1 follows from Lemma 3.2 and Lemma 3.5 below, by observing that since Er equals Er on
[−1, 1], E−1 −1
r equals Er on [Er (−1), Er (1)].
Lemma 3.2. Let r be a positive integer and let cr be the number
cr = min{ |Er (eit )| : t ∈ [0, 2π] } . (3.3)
Then the Taylor series at the origin of the function E−1
r has convergence radius at least cr .
For the proof of Lemma 3.2 we collect the following two basic facts (Proposition 3.3 and Proposi-
tion 3.4) about the function Er , which are consequences of Rouché’s theorem. The proof strategy can
also be found in the classical lectures [25] by Hurwitz.
Proposition 3.3. The function Er has exactly one root in D and this is a simple root located at the origin.
Proof. Since Er (0) = 0 and E0r (0) = Cr 6= 0, the function Er has a simple root at the origin. Recall that the
Taylor coefficients a1 , a2 , a3 , . . . of Er are nonnegative, that a1 = Cr and that Er (1) = Er (1) = ∑∞
k=1 ak = 1.
For any z ∈ ∂ D, the triangle inequality therefore gives
∞ ∞
|Er (z) −Cr z| = ∑ ak zk ≤ ∑ ak = 1 −Cr . (3.4)
k=2 k=2
In [11] it is shown that Cr increases with r. Now, since C1 = 2/π > 1/2, we have 1 −Cr < Cr and (3.4)
thus implies |Er (z) −Cr z| < Cr = |Cr z|. By Rouché’s theorem, the function Er therefore has the same
number (counting multiplicities) of zeros in D as the function Cr z does: one.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 88
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
Proposition 3.4. For any point z ∈ cr D there is exactly one point w ∈ D such that Er (w) = z.
Proof. If z = 0 the claim follows by Proposition 3.3. Fix a point z in the punctured disc cr D \ {0} and
define the function g by g(w) = Er (w) − z. For any w ∈ ∂ D on the boundary of the unit disc,
|Er (w) − g(w)| = |z| < cr ≤ |Er (w)| .
Hence, by Rouché’s Theorem the functions Er and g have an equal number of roots in D. It now follows
from Proposition 3.3 that the function g has exactly one root in the punctured unit disc D \ {0} and that
this is a simple root, which proves the claim.
Proof of Lemma 3.2. To get the Taylor series of E−1r at the origin we express this function as a contour
integral whose integrand we develop into a geometric series.
Let f be any function that is analytic in an open set of C that contains the closed unit disc D. For
z ∈ cr D consider the contour integral
1 E0r (w)
Z
I(z) = f (w) dw ,
2πi ∂D Er (w) − z
where the integral is over the counter-clockwise path around the unit circle. By Proposition 3.4 the
function g(w) = Er (w) − z has exactly one root in D and this is a root of order one. Hence, by the residue
theorem, I(z) is the value of f at the root of g. This root is E−1
r (z), so we have I(z) = f Er (z) . By
−1
taking the function f (w) = w we thus get
1 E0r (w)
Z
E−1
r (z) = w dw . (3.5)
2πi ∂D Er (w) − z
We expand the fraction appearing in the integrand of (3.5) as
E0r (w) E0 (w) z2
z
= r 1+ + + · · · . (3.6)
Er (w) − z Er (w) Er (w) Er (w)2
For any w ∈ ∂ D the above geometric series converges uniformly inside any disc c0r D, where c0r < cr , since
then |z| < cr and by the definition of cr (given in (3.3)), we have |Er (w)| ≥ cr . Substituting the fraction in
the integrand of (3.5) by the right-hand side of (3.6) gives the Taylor series at the origin
∞
E0r (w)
1
Z
∑ w dw zj , (3.7)
j=0 2πi ∂D Er (w) j+1
which converges to E−1
r (z) in cr D.
Lemma 3.5. Let r ≥ 2 and cr be as in (3.3). Then cr = |Er (i)|.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 89
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
Proof. Inspection of the definition of Er (given in (3.2)) shows that it suffices to consider the function
1/2, 1/2 it
Fr (t) = 2 F1 ;e
r/2 + 1
and show that |Fr (t)| is minimized at t = π. To this end we write |Fr (t)|2 = Rr (t)2 + Ir (t)2 , where Rr and
Ir are the real and the imaginary part of this function:
∞
(1/2)2k cos(kt)
Rr (t) = ∑ ,
k=0 (r/2 + 1)k k!
∞
(1/2)2k sin(kt)
Ir (t) = ∑ .
k=0 (r/2 + 1)k k!
We have Ir (π) = 0 so if Rr (t)2 attains a minimum at t = π we are done. Notice that for t ∈ [0, π] we
0
have Rr (π + t) = Rr (π − t). We claim that the derivative Rr (t)2 = 2Rr (t)R0r (t) is strictly negative for
t ∈ (0, π). Since Rr (t)2 is nonnegative and symmetric around π it then follows that its minimum on [0, π]
is indeed attained at π.
Claim 3.6. The function Rr is strictly positive on (0, π).
Proof. Vietoris’s theorem (see [5, Theorem 7.3.5]) states that for any positive integer n and real numbers
d1 , d2 , . . . , dn that satisfy d1 ≥ d2 ≥ · · · ≥ dn > 0 and 2kd2k ≤ (2k − 1)d2k−1 , k ≥ 1, we have
n
∑ dk cos(kt) > 0 for 0 < t < π .
k=0
It is easy to check that the series Rr (t) satisfies the conditions of Vietoris’s theorem with
(1/2)2k
dk =
(r/2 + 1)k k!
when r ≥ 2, so the claim follows.
Claim 3.7. The derivative R0r is strictly negative on (0, π).
Proof. The function R0r is given by
∞
(1/2)2k
R0r (t) = − ∑ k sin(kt) . (3.8)
k=0 (r/2 + 1)k k!
We show that the ratios appearing on the right-hand side of (3.8) are the moments of a finite
nonnegative (Borel) measure µ on [0, 1],
(1/2)2k
Z 1
= sk dµ(s) . (3.9)
(r/2 + 1)k k! 0
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 90
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
To this end, we write
! ! !
(1/2)2k Γ 2r + 1 Γ k + 12 Γ k + 12
= . (3.10)
Γ( 12 )2 Γ k + 2r + 1
(r/2 + 1)k k! Γ(k + 1)
For real numbers a, b > 0 such that a − b < 0, define the sequence (dk )∞
k=0 by dk = Γ(k + a)/Γ(k + b).
Let ∆dk = dk+1 − dk be the linear difference operator and for positive integer ` recursively define
∆` dk = ∆(∆`−1 dk ). By the formula Γ(x + 1) = xΓ(x), we have
k+a a−b
∆dk = − 1 dk = dk ,
k+b k+b
and induction on ` gives
(a − b)(a − b − 1) · · · (a − b − ` + 1)
∆ ` dk = dk .
(k + b)`
Since a − b is negative this shows that (−1)` ∆` dk ≥ 0 for every `, which is to say that the sequence
(dk )k is completely monotonic. Hausdorff’s theorem [20, pp. 223] says that a sequence is completely
monotonic if and only if it is the moment sequence of some finite nonnegative Borel measure on [0, 1]. In
other words, there exist independent [0, 1]-valued random variables X and Y and normalization constants
CX ,CY > 0 such that for every integer k ≥ 0, the right-hand side of (3.10) can be written as
Γ 2r + 1
CX E[X k ]CY E[Y k ] .
Γ( 12 )2
By defining the [0, 1]-valued random variable Z = XY , the above can be written as
CX CY (Γ(r/2 + 1)/Γ(1/2)2 )E[Z k ] ,
which gives (3.9).
With this, (3.8) becomes
∞ Z 1
R0r (t) = −∑ k
s dµ(s) k sin(kt)
k=0 0
Z 1
!
∞
= −
0
∑ sk k sin(kt) dµ(s)
k=0
!
s(1 − s2 ) sin(t)
Z 1
= − 2 dµ(s) < 0 , 0<t <π,
0 1 − 2s cos(t) + s2
where in last line we used the identity
∞
s(1 − s2 ) sin(t)
∑ sk k sin(kt) = 2 , 0 ≤ s < 1,
k=0 1 − 2s cos(t) + s2
which follows by differentiating the imaginary part of the Poisson kernel. This completes the proof.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 91
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
0
By combining the two claims, we get that Rr (t)2 = 2Rr (t)R0r (t) is strictly negative on (0, π), which
gives the result.
Theorem 3.1 follows by combining Lemmas 3.2 and 3.5.
4 Constructing new vectors
In this section we use the Taylor expansion of the inverse of the function Er to give a precise statement
and proof of Lemma 1.1; this is done in Lemma 4.1. For this we follow Krivine [33], who proved the
statement of the lemma in the case of bipartite graphs. We comment on how his ideas are related to our
construction, which can also deal with nonbipartite graphs, after we prove the lemma.
For the nonbipartite case we need to use the theta number, which is a graph parameter introduced by
Lovász [36]. Let G = (V, E) be a graph. The theta number of the complement of G, denoted by ϑ (G), is
the optimal value of the following semidefinite program:
n
ϑ (G) = min λ : Z ∈ RV0×V ,
Z(u, u) = λ − 1 for u ∈ V , (4.1)
o
Z(u, v) = −1 for {u, v} ∈ E .
It is known that the theta number of the complement of G provides a lower bound for the chromatic
number of G. This can be easily seen as follows. Any proper k-coloring of G defines a mapping √ of V
to the vertices of a (k − 1)-dimensional regular simplex whose vertices lie on a sphere of radius k − 1:
Vertices in the graph having the same color are sent to the same vertex in the regular simplex and vertices
of different colors are sent to different vertices in the regular simplex. The Gram matrix of these vectors
gives a feasible solution of (4.1).
Lemma 4.1. Let G = (V, E) be a graph with at least one edge. Given a function f : V → S|V |−1 , there is
a function g : V → S|V |−1 such that if u and v are adjacent,
Er g(u) · g(v) = β (r, G) f (u) · f (v) .
The constant β (r, G) is defined as the solution of the equation
∞
1
∑ |b2k+1 |β (r, G)2k+1 = ϑ (G) − 1 , (4.2)
k=0
where the coefficients b2k+1 are those of the Taylor series (3.1).
Recall from Theorem 3.1 and Lemma 3.5 that the series (3.1) has convergence radius at least
cr = |Er (i)|. The proof of Lemma 4.1 relies on the following proposition.
Proposition 4.2. Let r be a positive integer and G be a graph with at least one edge. Then, for any
t ∈ [−1, 1], the series
∞ 2k+1
∑ b2k+1 t β (r, G)
k=0
converges to Er−1 t β (r, G) .
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 92
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
Proof. As described in the beginning of Section 3, the case r = 1 follows from the fact that in that case
the convergence radius of the series (3.1) is infinity. For r ≥ 2, we consider the series
∞
f (t) = ∑ |b2k+1 |t 2k+1 . (4.3)
k=0
Let β = β (r, G) be as in (4.2). To prove the claim it suffices to show that β indeed exists and that it lies
in an interval where the series (3.1) converges to Er−1 . Since G has at least one edge, we have ϑ (G) ≥ 2.
Hence, by (4.2) the number β should satisfy f (β ) ≤ 1. Note that f is well defined for any t ∈ (−cr , cr ),
which follows from Theorem 3.1 and Lemma 3.5 showing that the series (4.3) converges in cr D.
We distinguish two cases based on the behavior of f at the point cr . The first case is: f (cr ) = +∞.
In this case notice that f (0) = 0 and that f is continuous and increasing on the interval [0, cr ). Since
f (cr ) > 1 it follows that there exists a t ∈ (0, cr ) such that f (t) = 1. Now, since 0 ≤ f (β ) ≤ 1, we see
that β exists and lies in the radius of convergence of the series (3.1).
The second case is that f (cr ) is finite. Recall that the Taylor series at the origin of the complex
function E−1 r is given by
∞
∑ b2k+1 z2k+1 . (4.4)
k=0
Then, since for any z ∈ D the triangle inequality gives
∞
∑ b2k+1 (cr z)2k+1 ≤ f (cr ) ,
k=0
the series (4.4) converges absolutely in the closed disc cr D and thus defines a continuous function
g : cr D → C. By Lemma 3.2 g equals E−1 r in the open disc cr D, but by continuity of both Er and g, this
−1
equality must hold even in its closure cr D. In particular, this implies that the series (3.1) converges to
Er−1 on [−cr , cr ].
Next, we argue that β ≤ cr . Since Er is an odd function, and using Lemma 3.5,
∞ ∞
Er (i) = ∑ a2k+1 i2k+1 = i ∑ a2k+1 (−1)k = ±icr . (4.5)
k=0 k=0
Suppose that Er (i) = icr holds (the other case Er (i) = −icr follows by the same argument). Then, the
above discussion implies that applying E−1
r to both sides of (4.5) gives
∞ ∞
i = Er )−1 (icr ) = ∑ b2k+1 (icr )2k+1 = i ∑ b2k+1 (−1)k c2k+1
r . (4.6)
k=0 k=0
Taking absolute values of the left- and right-hand sides of (4.6) gives
∞ ∞
1 = i ∑ b2k+1 (−1)k c2k+1
r ≤ ∑ |b2k+1 |c2k+1
r = f (cr ) .
k=0 k=0
Hence, f (β ) ≤ 1 ≤ f (cr ) and from the fact that f is increasing and zero at the origin we conclude
that β exists and that β ∈ [0, cr ].
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 93
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
Now we prove Lemma 4.1.
Proof of Lemma 4.1. We construct the vectors g(u) ∈ S|V |−1 by constructing vectors R(u) in an infinite-
dimensional Hilbert space whose inner product matrix coincides with the one of the g(u). We do this in
three steps.
In the first step, set H = R|V | and consider the Hilbert space
∞
H= H ⊗(2k+1) .
M
k=0
For a unit vector x ∈ H, consider the vectors S(x), T (x) ∈ H given componentwise by
q
S(x)k = |b2k+1 |β (r, G)2k+1 x⊗(2k+1)
and q
T (x)k = sign(b2k+1 ) |b2k+1 |β (r, G)2k+1 x⊗(2k+1) .
From Proposition 4.2 it follows that for any vectors x, y ∈ S|V |−1 we have
S(x) · T (y) = Er−1 (β (r, G)x · y) ,
and moreover ∞
1
S(x) · S(x) = T (x) · T (x) = ∑ |b2k+1 |β (r, G)2k+1 = .
k=0 ϑ (G) − 1
In the second step, let λ = ϑ (G), and Z be an optimal solution of (4.1). We have λ ≥ 2 since G has
at least one edge. Let J denote the |V | × |V | all-ones matrix and set
(λ − 1)(J + Z) (λ − 1)J − Z
A= and B= ,
2λ 2λ
and consider the matrix
A B
U= .
B A
By applying a Hadamard transformation
1 I I 1 I I A+B 0
√ U√ =
2 I −I 2 I −I 0 A−B
one sees that U is positive semidefinite, since both A + B and A − B are positive semidefinite. Define
s : V → R2|V | and t : V → R2|V | so that
s(u) · s(v) = t(u) · t(v) = A(u, v) and s(u) · t(v) = B(u, v) .
Matrix U is the Gram matrix of vectors s(u) u∈V and t(v) v∈V . It follows that these maps have the
following properties:
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 94
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
1. s(u) · t(u) = 0 for all u ∈ V ,
2. s(u) · s(u) = t(u) · t(u) = (ϑ (G) − 1)/2 for all u ∈ V ,
3. s(u) · s(v) = t(u) · t(v) = 0 whenever {u, v} ∈ E,
4. s(u) · t(v) = s(v) · t(u) = 1/2 whenever {u, v} ∈ E.
In the third step we combine the previous two. We define the vectors
R(u) = s(u) ⊗ S( f (u)) + t(u) ⊗ T ( f (u)) .
For adjacent vertices u, v ∈ V we have
R(u) · R(v) = Er−1 (β (r, G) f (u) · f (v)) ,
and moreover the R(u) are unit vectors. Hence, one can use the Cholesky decomposition of the matrix
(R(u) · R(v))u,v∈V ∈ RV0×V to define the desired function g : V → S|V |−1 .
We conclude this section with a few remarks on Lemma 4.1 and its proof:
1. To approximate the Gram matrix (R(u) · R(v)) it is enough to compute the series expansion of Er−1
and the matrix U to the desired precision. The latter is found by solving a semidefinite program.
2. Krivine proved the statement of the lemma in the case r = 1 and for bipartite graphs G; then,
ϑ (G) = 2 holds. Here, one only needs the first step of the proof. Also, β (1, G) can be computed
analytically. We have E1−1 (t) = sin(π/2t) and
∞
(π/2)2k+1
∑ (−1)2k+1 (2k + 1)! t 2k+1 = sinh(π/2t) .
k=0
√
Hence, β (1, G) = 2 arcsinh(1)/π = 2 ln(1 + 2)/π.
3. In the second step one can also work with any feasible solution of the semidefinite program (4.1).
For instance one can replace ϑ (G) in the lemma by the chromatic number χ(G) albeit getting a
potentially weaker bound.
4. Alon, Makarychev, Makarychev, and Naor [3] also gave an upper bound for K(1, G) using the theta
number of the complement of G. They prove that
K(1, G) ≤ O(log ϑ (G)) ,
which is much better than our result in the case of large ϑ (G). However, our bound is favourable
when ϑ (G) is small. In Section 5 we generalize the methods of Alon, Makarychev, Makarychev,
and Naor [3] to obtain better upper bounds on K(r, G) for r ≥ 2 and large ϑ (G).
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 95
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
5 Better bounds for large chromatic numbers
For graphs with large chromatic number, or more precisely with large ϑ (G), our bounds on K(r, G)
proved above can be improved using the techniques of Alon, Makarychev, Makarychev, and Naor [3]. In
this section, we show how their bounds on K(1, G) generalize to higher values of r.
Theorem 5.1. For a graph G = (V, E) and integer 1 ≤ r ≤ log ϑ (G), we have
log ϑ (G)
K(r, G) ≤ O .
r
Proof. It suffices to show that for any matrix A : V ×V → R, we have
r
SDPr (G, A) ≥ Ω SDP∞ (G, A) .
log ϑ (G)
Fix a matrix A : V ×V → R. Let f : V → S|V |−1 be optimal for SDP∞ (G, A), so that
∑ A(u, v) f (u) · f (v) = SDP∞ (G, A) .
{u,v}∈E
Let λ = ϑ (G), and Ze : V × V → R be an optimal solution of (4.1). Since the matrix Ze is positive
semidefinite we get from its Gram decomposition column vectors z(u) ∈ R|V | for u ∈ V . From the
properties of Ze it follows that z(u) · z(u) = λ − 1 and z(u) · z(v) = −1 if {u, v} ∈ E. Denote by 0 ∈ R|V |
the all-zero vector. We now define vectors s(u),t(u) ∈ R2|V |+1 as
z(u) 0
1 1
s(u) = √ 0 and t(u) = √ z(u) .
λ 1 λ 1
It is easy to verify that these vectors have the following dot products:
1. s(u) · s(u) = t(u) · t(u) = 1 for all u ∈ V .
2. s(u) · t(u) = 1/λ for all u, v ∈ V .
3. s(u) · s(v) = t(u) · t(v) = 0 for all {u, v} ∈ E.
Let H be the Hilbert space of vector-valued functions h : Rr×|V | → Rr with inner product
(g, h) = E[g(Z) · h(Z)] ,
where the expectation is taken over random r × |V | matrices Z whose entries are i. i. d. N(0, 1/r) random
variables.
Let R ≥ 2 be some real number to be set later. Define for every u ∈ V the function gu ∈ H by
Z f (u) if kZ f (u)k ≤ R,
R
gu (Z) = Z f (u)
kZ f (u)k otherwise.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 96
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
Notice that for every matrix Z ∈ Rr×|V | , the vector gu (Z) ∈ Rr has Euclidean norm at most 1. It follows
by linearity of expectation that
SDPr (G, A) ≥ E ∑ A(u, v) gu (Z) · gv (Z) = ∑ A(u, v)(gu , gv ) .
{u,v}∈E {u,v}∈E
We proceed by lower bounding the right-hand side of the above inequality.
Based on the definition of gu we define two functions h0u , h1u ∈ H by
Z f (u) Z f (u)
h0u (Z) = + gu (Z) and h1u (Z) = − gu (Z) .
R R
For every u ∈ V , define the function Hu ∈ R2|V | ⊗ H by
1
Hu = s(u) ⊗ h0u + 2λ t(u) ⊗ h1u .
4
We expand the inner products (gu , gv ) in terms of f (u) · f (v) and hHu , Hv i.
Claim 5.2. For every {u, v} ∈ E we have
1
(gu , gv ) = f (u) · f (v) − hHu , Hv i .
R2
Proof. Simply expanding the inner product hHu , Hv i gives
s(u) · s(v) 0 0
(hu , hv ) + 4λ 2 t(u) · t(v) (h1u , h1v )
hHu , Hv i =
16
λh i
s(u) · t(v) (h0u , h1v ) + t(u) · s(v) (h1u , h0v ) .
+
2
It follows from property 3 of s and t that the above terms involving s(u) · s(v) and t(u) · t(v) vanish. By
property 2, the remaining terms reduce to
1 0 1 1 Z f (u)
Z f (v)
1 0
(hu , hv ) + (hu , hu ) = E + gu (Z) · − gv (Z)
2 2 R R
1 Z f (u) Z f (v)
+ E − gu (Z) · + gv (Z) .
2 R R
Expanding the first expectation gives
1 T T Z f (u) Z f (v)
E[ f (u) Z Z f (v)] − (gu , gv ) − E · gv (Z) + E gu (Z) ·
R2 R R
and expanding the second gives
1 T T Z f (u) Z f (v)
E[ f (u) Z Z f (v)] − (gu , gv ) + E · gv (Z) − E gu (Z) · .
R2 R R
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 97
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
Adding these two gives that the last two terms cancel. Since E[Z T Z] = I, what remains equals
1
f (u) · f (v) − (gu , gv ) ,
R2
which proves the claim.
From the above claim it follows that
1
∑ A(u, v)(gu , gv ) = R2 SDP∞ (G, A) − ∑ A(u, v)hHu , Hv i
{u,v}∈E {u,v}∈E
1 2
≥ − max kHu k SDP∞ (G, A) ,
R2 u∈V
where kHu k2 = hHu , Hu i.
By the triangle inequality, we have for every u ∈ V ,
2 2
1 0 1 1 Z f (u)
kHu k2 ≤ kh k + 2λ kh1u k ≤ + 2λ R E − gu (Z) .
4 u R2 2 R
By the definition of gu , the vectors Z f (u) and gu are parallel. Moreover, they are equal if kZ f (u)k ≤ R.
Since f (u) is a unit vector, the r entries of the random vector Z f (u) are i. i. d. N(0, 1/r) random variables.
Hence,
Z kxk
Z f (u) r r/2 2
E − gu (Z) = 1[kxk ≥ R] −1 e−rkxk /2 dx
R Rr R 2π
Z ∞Z ρ r r/2 2
= ρ r−1 −1 e−rρ /2 dρ d ω̃r (ξ )
R S r−1 R 2π
rr/2
Z ∞
2
≤ r
ρ r e−rρ /2 dρ ,
RΓ 2 R
where ω̃r is the unique rotationally invariant measure on Sr−1 , normalized so that ω̃r (Sr−1 ) = rr/2 /Γ(r/2).
Using a substitution of variables, we get
1 2 (r+1)/2 r + 1 rR2
Z ∞
2
ρ r e−rρ /2 dρ = Γ , ,
R 2 r 2 2
where Γ(a, x) is the lower incomplete Gamma function [5, Eq. (4.4.5)].
Collecting the terms from above then gives the bound
!2
1 1 2(r+1)/2 r + 1 rR 2
SDPr (G, A) ≥ 2 1 − +λ √ r
Γ , SDP∞ (G, A) . (5.1)
R 2 rΓ 2 2 2
The bound in the theorem follows by setting R as small as possible such that the above factor between
brackets is some positive constant.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 98
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
By Stirling’s formula, there is a constant C1 > 0 such that Γ(x) ≥ C1 e−x xx−1/2 holds (see for example
Abramowitz and Stegun [2, Eq. (6.1.37)]). Hence, for some constants c,C > 0, we have
2(r+1)/2 c r/2
√ ≤ C . (5.2)
rΓ 2r
r
The power series of the incomplete gamma function [2, Eq. (6.5.32)] gives that if a ≤ x, for some
constant C2 > 0, the inequality Γ(a, x) ≤ C2 xa e−x holds. As R ≥ 2, for some constants d, D > 0, we have
r/2
r + 1 rR2 √
r
Γ , ≤D r 2 . (5.3)
2 2 dR
Putting together estimates (5.2) and (5.3) gives
2(r+1)/2 r + 1 rR2 √ c r/2
λ√ Γ , ≤ CD rλ .
rΓ 2r 2 2 dR
2
Since r ≤ log λ there is some constant C0 such that for R2 = C0 log λ /r, the above value is less than
1/4. It follows that for this value of R, inequality (5.1) is nontrivial and we get the result.
6 Numerical computation of Table 1
Table 1 shows numerical estimates of 1/β (r, G) which can be obtained using the Taylor polynomials of f
given by
M
fM (β ) = ∑ |b2k+1 |β 2k+1
k=0
for positive integers
M. The numerical estimates of β (r, G) can be obtained by solving for fM (β ) =
1/ ϑ (G) − 1 using a computer program such as the PARI/GP [1] code given below. We strongly believe
that all the digits of the table are correct but our computations are just numerical and do not yield a formal
proof. Since we also believe that our bound is not sharp, K(r, G) < β (r, G)−1 , we did not make the effort
to transform the numerical computations into rigorous proofs.
Acknowledgements
The first author thanks Stamatis Koumandos for helpful suggestions regarding the proof of Claim 3.7. The
third author thanks Assaf Naor for helpful comments, and the Institute for Pure & Applied Mathematics
at UCLA for its hospitality and support during the program “Modern Trends in Optimization and Its
Application,” September 17–December 17, 2010. We thank the anonymous referees for many helpful
comments and suggestions.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 99
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
Source code 1 PARI/GP [1] code to generate Table 1.
\p 100
M = 100
r = 2
rhs = 1
Er = 0 + O(t^(2*n+2))
for(k=0, M, Er = Er + (gamma(1/2+k)^2 *
gamma(r/2+1))/(gamma(1/2)^2 * gamma(r/2+1+k) * gamma(k+1)) *
t^(2*k+1))
Er = 2/r * (gamma((r+1)/2)/gamma(r/2))^2 * Er
Erinv = serreverse(Er)
fpol = 0
for(k=0, M, fpol = fpol + abs(polcoeff(Erinv,2*k+1))*t^(2*k+1))
beta_rG = polroots(fpol-rhs)[1]
References
[1] PARI/GP computer algebra system, version 2.5.3, Bordeaux, 2012. PARI/GP. 99, 100
[2] M ILTON A BRAMOWITZ AND I RENE A NN S TEGUN: Handbook of mathematical functions with
formulas, graphs, and mathematical tables. U.S. Department of Commerce, National Bureau of
Standards, 1964. Available at Internet Archive. 99
[3] N OGA A LON , KONSTANTIN M AKARYCHEV, Y URY M AKARYCHEV, AND A SSAF NAOR:
Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006. Preliminary version in STOC’05.
[doi:10.1007/s00222-005-0465-9] 78, 79, 83, 95, 96
[4] N OGA A LON AND A SSAF NAOR: Approximating the cut-norm via Grothendieck’s in-
equality. SIAM J. Comput., 35(4):787–803, 2006. Preliminary version in STOC’04.
[doi:10.1137/S0097539704441629] 79
[5] G EORGE E. A NDREWS , R ICHARD A SKEY, AND R ANJAN ROY: Special Functions. Vol-
ume 71 of Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, 1999.
[doi:10.1017/CBO9781107325937] 84, 86, 87, 90, 98
[6] S ANJEEV A RORA , E LI B ERGER , E LAD H AZAN , G UY K INDLER , AND M ULI S AFRA: On non-
approximability for quadratic programs. In Proc. 46th FOCS, pp. 206–215. IEEE Comp. Soc. Press,
2005. See also at ECCC. [doi:10.1109/SFCS.2005.57] 79
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 100
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
[7] A LAIN A SPECT, P HILIPPE G RANGIER , AND G ÉRARD ROGER: Experimental tests of
realistic local theories via Bell’s theorem. Phys. Rev. Lett., 47(7):460–463, 1981.
[doi:10.1103/PhysRevLett.47.460] 80
[8] J OHN S. B ELL: On the Einstein-Podolsky-Rosen paradox. Physics, 1(3):195–200, 1964. Available
at Wissenschaftstheorie und Wissenschaftsgeschichte. 80
[9] A HARON B EN -TAL AND A RKADI N EMIROVSKI: On tractable approximations of uncertain linear
matrix inequalities affected by interval uncertainty. SIAM J. on Optim., 12(3):811–833, 2002.
[doi:10.1137/S1052623400374756] 79
[10] M ARK B RAVERMAN , KONSTANTIN M AKARYCHEV, Y URY M AKARYCHEV, AND A SSAF NAOR:
The Grothendieck constant is strictly smaller than Krivine’s bound. In Proc. 52nd FOCS, pp.
453–462. IEEE Comp. Soc. Press, 2011. See also at arXiv. [doi:10.1109/FOCS.2011.77] 83
[11] J OP B RIËT, H ARRY B UHRMAN , AND B EN T ONER: A generalized Grothendieck inequality and
nonlocal correlations that require high entanglement. Comm. Math. Phys., 305(3):827–843, 2011.
[doi:10.1007/s00220-011-1280-3] 78, 79, 88
[12] J OP B RIËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN: The positive
semidefinite Grothendieck problem with rank constraint. In Proc. 37th Internat. Colloq. on Automata,
Languages and Programming (ICALP’10), pp. 31–42. Springer, 2010. [doi:10.1007/978-3-642-
14165-2_4] 85
[13] J OP B RIËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN: The
Grothendieck problem with rank constraint. In Proceedings of the 19th Symposium on Math-
ematical Theory of Networks and Systems (MTNS’10), pp. 111–113, 2010. MTNS. 83
[14] M OSES C HARIKAR AND A NTHONY W IRTH: Maximizing quadratic programs: Extending
Grothendieck’s inequality. In Proc. 45th FOCS, pp. 54–60. IEEE Comp. Soc. Press, 2004.
[doi:10.1109/FOCS.2004.39] 79
[15] R ICHARD C LEVE , P ETER H ØYER , B ENJAMIN T ONER , AND J OHN WATROUS: Consequences and
limits of nonlocal strategies. In Proc. 19th IEEE Conf. on Computational Complexity (CCC’04), pp.
236–249. IEEE Comp. Soc. Press, 2004. See also at arXiv. [doi:10.1109/CCC.2004.1313847] 80
[16] A LEXANDER DAVIE: Lower bound for KG . Unpublished, 1984. 83
[17] J OE D IESTEL , JAN H. F OURIE , AND J OHAN S WART: The metric theory of tensor products:
Grothendieck’s résumé revisited. Amer. Math. Soc., 2008. AMS. 84
[18] A LBERT E INSTEIN , B ORIS P ODOLSKY, AND NATHAN ROSEN: Can quantum-mechanical de-
scription of physical reality be considered complete? Physical Review, 47(10):777–780, 1935.
[doi:10.1103/PhysRev.47.777] 80
[19] A RTHUR E RDÉLYI , W ILHELM M AGNUS , F RITZ O BERHETTINGER , AND F RANCESCO G. T RI -
COMI : Tables of integral transforms, Vol. 1. McGraw-Hill, New York, 1954. 87
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 101
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
[20] W ILLIAM F ELLER: An introduction to probability theory and applications. Volume II. John Wiley
and Sons, New York, 1966. 85, 91
[21] DAVID J. H. G ARLING: Inequalities: a journey into linear analysis. Cambridge Univ. Press, 2007.
[doi:10.1017/CBO9780511755217] 79
[22] M ICHEL X. G OEMANS AND DAVID P. W ILLIAMSON: Improved approximation algorithms for
maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–
1145, 1995. Preliminary version in STOC’94. [doi:10.1145/227683.227684] 79, 84
[23] A LEXANDER G ROTHENDIECK: Résumé de la théorie métrique des produits tensoriels topologiques
(French). Bol. Soc. Mat. São Paulo, 8:1–79, 1953. Available at Instituto de Matemática e Estatística
da Universidade de São Paulo. 78, 84
[24] U FFE H AAGERUP: A new upper bound for the complex Grothendieck constant. Israel Journal of
Mathematics, 60(2):199–224, 1987. [doi:10.1007/BF02790792] 78, 83, 85, 88
[25] A DOLF H URWITZ: Vorlesungen über allgemeine Funktionentheorie und elliptische Funktionen.
Spring, 1925. Available at Göttinger Digitalisierungszentrum. 88
[26] G RAHAM J. O. JAMESON: Summing and nuclear norms in Banach space theory. Cambridge Univ.
Press, 1987. [doi:10.1017/CBO9780511569166] 79
[27] S UBHASH K HOT AND A SSAF NAOR: Linear equations modulo 2 and the L1 diameter of
convex bodies. SIAM J. Comput., 38(4):1448–1463, 2008. Preliminary version in FOCS’07.
[doi:10.1137/070691140] 79
[28] S UBHASH K HOT AND A SSAF NAOR: Approximate kernel clustering. Mathematika, 55(1-2):129–
165, 2009. Preliminary version in FOCS’08. [doi:10.1112/S002557930000098X] 79
[29] S UBHASH K HOT AND A SSAF NAOR: Sharp kernel clustering algorithms and their associated
Grothendieck inequalities. Random Structures & Algorithms, 42(3):269–300, 2013. Preliminary
version in SODA’10. See also at arXiv. [doi:10.1002/rsa.20398] 79
[30] S UBHASH K HOT AND RYAN O’D ONNELL: SDP gaps and UGC-hardness for Max-Cut-
Gain. Theory of Computing, 5(4):83–117, 2009. Preliminary version in FOCS’06.
[doi:10.4086/toc.2009.v005a004] 79, 83
[31] G UY K INDLER , A SSAF NAOR , AND G IDEON S CHECHTMAN: The UGC hardness threshold of
the L p Grothendieck problem. Math. Oper. Res., 35(2):267–283, 2010. Preliminary version in
SODA’08. [doi:10.1287/moor.1090.0425] 79
[32] H ERMANN K ÖNIG: On an extremal problem originating in questions of unconditional convergence.
In W. H AUSSMANN , K. J ETTER , AND M. R EIMER, editors, Recent Progress in Multivariate
Approximation: 4th Internat. Conf., Witten-Bommerholz (Germany), Sep. 2000, volume 137 of
Internat. Ser. Numer. Math., pp. 185–192. Birkhäuser, 2001. [doi:10.1007/978-3-0348-8272-9_14]
85
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 102
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
[33] J EAN -L OUIS K RIVINE: Constantes de Grothendieck et fonctions de type positif sur les sphères.
Advances in Math., 31(1):16–30, 1979. [doi:10.1016/0001-8708(79)90017-3] 83, 92
[34] J ORAM L INDENSTRAUSS AND A LEKSANDER P EŁCZY ŃSKI: Absolutely summing operators in
L p -spaces and their applications. Studia Math., 29(3):275–326, 1968. Available at EuDML. 78
[35] NATI L INIAL AND A DI S HRAIBMAN: Lower bounds in communication complexity based on
factorization norms. Random Structures & Algorithms, 34(3):368–394, 2009. Preliminary version
in STOC’07. [doi:10.1002/rsa.20232] 79
[36] L ÁSZLÓ L OVÁSZ: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1–7,
1979. [doi:10.1109/TIT.1979.1055985] 92
[37] A LEXANDRE M EGRETSKI: Relaxations of quadratic programs in operator theory and system
analysis. In Systems, Approximation, Singular Integral Operators, and Related Topics: International
Workshop on Operator Theory and Applications (IWOTA’00), volume 129, pp. 365–392. Birkhäuser
Basel, 2001. [doi:10.1007/978-3-0348-8362-7_15] 79
[38] A SSAF NAOR AND O DED R EGEV: Krivine schemes are optimal. Technical report, 2012. To appear
in Proc. AMS. [arXiv:1205.6415] 83
[39] A RKADI N EMIROVSKI , C ORNELIS ROOS , AND TAMÁS T ERLAKY: On maximization of quadratic
form over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463–
473, 1999. [doi:10.1007/s101070050100] 79
[40] Y URII N ESTEROV: Semidefinite relaxations and nonconvex quadratic optimization. Optimization
Methods and Software, 9(1-3):141–160, 1998. [doi:10.1080/10556789808805690] 79
[41] G ILLES P ISIER: Factorization of linear operators and geometry of Banach spaces. Number 60 in
CBMS regional conference series. Amer. Math. Soc., Providence, Rhode Island, 1986. 79
[42] P RASAD R AGHAVENDRA AND DAVID S TEURER: Towards computing the Grothendieck constant.
In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 525–534. ACM Press,
2009. [ACM:1496770.1496828] 79
[43] JAMES R EEDS: A new lower bound on the real Grothendieck constant. Available at author’s home
page, 1991. 83
[44] O DED R EGEV AND B EN T ONER: Simulating quantum correlations with finite commu-
nication. SIAM J. Comput., 39(4):1562–1580, 2009. Preliminary version in FOCS’07.
[doi:10.1137/080723909] 79
[45] H ARRY E UGENE S TANLEY: Spherical model as the limit of infinite spin dimensionality. Physical
Review, 176(2):718–722, 1968. [doi:10.1103/PhysRev.176.718] 79
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 103
J OP B RI ËT, F ERNANDO M ÁRIO DE O LIVEIRA F ILHO , AND F RANK VALLENTIN
[46] B ORIS T SIRELSON: Quantum analogues of the Bell inequalities. The case of two spatially separated
domains. J. Soviet Math., 36:557–570, 1987. Translated from Problems of the Theory of Probability
Distributions IX, Math. Inst. Steklov (LOMI), 142 (1985), pp. 174–194. (In Russian.) Available at
author’s homepage. 79, 80
[47] L IEVEN VANDENBERGHE AND S TEPHEN B OYD: Semidefinite programming. SIAM Review,
38(1):49–95, 1996. [doi:10.1137/1038003] 79
AUTHORS
Jop Briët
Postdoc
Courant Institute
New York University
jop briet cims nyu edu
http://cims.nyu.edu/~jb4808/
Fernando Mário de Oliveira Filho
Assistant professor
Instituto de Matemática e Estatística
Universidade de São Paulo
fmario gmail com
http://www.ime.usp.br/~fmario/
Frank Vallentin
Professor
Mathematisches Institut
Universität zu Köln
frank vallentin uni-koeln de
http://www.mi.uni-koeln.de/opt/frank-vallentin/
ABOUT THE AUTHORS
J OP B RIËT is a postdoc at the Courant Institute of New York University. He received
his Ph. D. from C.W.I. and the University of Amsterdam in 2011, under the wonderful
supervision Harry Buhrman. He is very grateful to Peter Høyer, who coached him into
theoretical computer science and encouraged him to pursue a Ph. D. degree after obtaining
B. Sc. and M. Sc. degrees in physics at the University of Calgary. He likes problems that
lie in the intersection of theoretical computer science and pure mathematics. He recently
started taking yoga classes where he tries handstands and does many downward dogs.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 104
G ROTHENDIECK I NEQUALITIES FOR S EMIDEFINITE P ROGRAMS WITH R ANK C ONSTRAINT
F ERNANDO M ÁRIO DE O LIVEIRA F ILHO is assistant professor at the Department of
Computer Science of the Institute of Mathematics and Statistics of the University of
São Paulo. In 2009, he received his Ph. D. in mathematics and computer science from
the University of Amsterdam after working for 4 years at the Centrum Wiskunde &
Informatica under Alexander Schrijver and Frank Vallentin. Past appointments include a
postdoc at Tilburg University and a postdoc at the Freie Universität Berlin.
F RANK VALLENTIN is a professor of applied mathematics and computer science at Uni-
versität zu Köln. In 2003 he received his Ph. D. in mathematics from Technische Uni-
versität München under the supervision of Jürgen Richter-Gebert. Past appointments
include assistant and associate professor at Technische Universiteit Delft, postdoc at
Centrum Wiskunde & Informatica in Amsterdam and postdoc at the Hebrew University
of Jerusalem.
T HEORY OF C OMPUTING, Volume 10 (4), 2014, pp. 77–105 105