Authors Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289
www.theoryofcomputing.org
SDP Gaps from Pairwise Independence
Siavosh Benabbas Konstantinos Georgiou Avner Magen ∗
Madhur Tulsiani†
Received: April 14, 2010; revised: November 8, 2011; published: June 21, 2012.
Abstract: We consider the problem of approximating fixed-predicate constraint satisfaction
problems (MAX k-CSPq (P)), where the variables take values from [q] = {0, 1, . . . , q − 1},
and each constraint is on k variables and is defined by a fixed k-ary predicate P. Familiar
problems like MAX 3-SAT and MAX-CUT belong to this category. Austrin and Mossel
recently identified a general class of predicates P for which MAX k-CSPq (P) is hard to
approximate. They study predicates P : [q]k → {0, 1} such that the set of assignments
accepted by P contains the support of a balanced pairwise independent distribution over the
domain of the inputs. We refer to such predicates as promising. Austrin and Mossel show
that for any promising predicate P, the problem MAX k-CSPq (P) is Unique-Games-hard to
approximate better than the trivial approximation obtained by a random assignment.
We give an unconditional analogue of this result in a restricted model of computation.
We consider the hierarchy of semidefinite relaxations of MAX k-CSPq (P) obtained by
augmenting the canonical semidefinite relaxation with the Sherali-Adams hierarchy. We show
that for any promising predicate P, the integrality gap remains the same as the approximation
ratio achieved by a random assignment, even after Ω(n) levels of this hierarchy.
∗ Funded in part by NSERC.
† Supported by the NSF grant CCF-083279.
ACM Classification: F.2.2, F.1.3, G.1.6, F.2.3
AMS Classification: 68Q17, 68W25, 68W20, 90C59
Key words and phrases: semidefinite and linear programming hierarchies, integrality gaps, constraint
satisfaction
2012 Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v012
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
We also introduce a new general set of techniques to define consistent “local distributions”
over partial assignments to variables in the problem. Defining such distributions has often
been the crux of proving lower bounds on integrality gaps for hierarchies like the ones we
consider.
1 Introduction
A constraint satisfaction problem (CSP) is defined by a set of constraints on a set of q-valued variables.
In the maximization version (MAX-CSP) one tries to maximize the number of constraints that can
be simultaneously satisfied. In this paper, we consider the most commonly studied families of CSPs,
denoted by MAX k-CSPq (P), defined as follows. The variables take values over the fixed alphabet
[q] = {0, 1, . . . , q − 1}. All constraints are defined by a single predicate P : [q]k → {0, 1} and have the
form P(x1 + b1 mod q, . . . , xk + bk mod q) for bi ∈ [q]. For instance, MAX 3-SAT is the same as MAX
3-CSP2 (OR3 ), where OR3 denotes the 3-variable OR function. We refer to the terms xi + bi mod q as
literals,1 generalizing from the Boolean case, where the literals are xi and ¬xi = xi + 1 mod 2.
Given a predicate P, an instance of the MAX k-CSPq (P) problem is a collection of constraints as
above and the objective is to maximize the number of constraints that can be satisfied simultaneously. As
special cases, we obtain many well-studied MAX-CSP problems, e. g., MAX k-SAT, MAX k-XOR, MAX
k-LINq (systems of mod q linear equations with k variables per equation), etc. Note that MAX 2-LIN2
includes MAX-CUT. We use MAX k-CSPq to denote the union of the classes MAX k-CSPq (P) over all
P : [q]k → {0, 1}.
The MAX k-CSPq problem is NP-hard for any k ≥ 2, q ≥ 2. A lot of effort has been devoted to
determining the true approximability threshold of the problem as a function of k and q. For the Boolean
case (q = 2), Samorodnitsky √ and Trevisan [25] proved that
√ the problem is hard to approximate within
a factor less than 2 /2 , which was improved to 2 /2 2k by Engebretsen and Holmerin [12]. Later
k 2 k k
Samorodnitsky and Trevisan [24] showed that it is Unique-Games-hard (UG-hard) to approximate the
same problem within a factor less than 2k /2dlog k+1e . For the general case of q-valued variables (MAX
k-CSPq ), Guruswami and Raghavendra [16] proved UG-hardness of approximation within a factor less
than qk /(kq2 ) when q is a prime.
Austrin and Mossel [5] studied the complexity of MAX k-CSPq (P) for predicates P : [q]k → {0, 1}
such that the set of accepted inputs P−1 (1) contains the support of a balanced pairwise independent
distribution on [q]k . We shall refer to such predicates as promising. In a very general result, which
(assuming the Unique Games Conjecture) subsumes all the above, Austrin and Mossel [5] showed that
for a promising predicate P, the MAX k-CSPq (P) problem is UG-hard to approximate within a factor
less than qk /|P−1 (1)|. Considering that a random assignment satisfies a |P−1 (1)|/qk fraction of all the
constraints, this is the strongest result one can get for such P. Using appropriate choices for the predicate
P, this then implies a hardness ratio of qk /((1 + o(1))kq2 ) for MAX k-CSPq for any q ≥ 2, a ratio of
qk /(kq(q − 1)) when q is a prime power, and 2k /(k + O(k0.525 )) for q = 2.
In this paper, we study the inapproximability of MAX k-CSPq (P) for promising predicates P, in a
restricted model of computation. The model we consider is the hierarchy of semidefinite relaxations
1 We believe this terminology was introduced by [5] (see also [4]).
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 270
SDP G APS FROM PAIRWISE I NDEPENDENCE
of MAX k-CSPq (P), given by an application of the Sherali-Adams [29] strengthenings of the canonical
semidefinite relaxation of MAX k-CSPq (P). We give an unconditional analogue of the result of Austrin
and Mossel in this hierarchy, demonstrating that even after Ω(n) levels of this hierarchy, the integrality
gap remains at least qk /|P−1 |, which is the approxiation ratio achieved by a random assignment. (The
implied constant in the Ω(n) notation depends on k and q.)
Hierarchies of linear and semidefinite programs
A standard approach in approximating NP-hard problems, and therefore MAX k-CSPq , is to formulate the
problem as a 0-1 integer program and then relax the integrality condition to get a linear (or semidefinite)
program which can be solved efficiently. The quality of such an approach is intimately related to the
integrality gap of the relaxation, namely, the ratio between the optimum of the relaxation and that of the
integer program.
Several methods (or procedures) were developed in order to obtain tightenings of relaxations in a
systematic manner. These procedures give a sequence or a hierarchy of increasingly tighter relaxations of
the starting program. The commonly studied ones include the hierarchies defined by Lovász-Schrijver [19],
Sherali-Adams [29], and Lasserre [17] (see [18] for a comparison). Stronger relaxations in the sequence
are referred to as higher levels of the hierarchy. It is known for all these hierarchies that for a starting
program with n variables, the program at level n has integrality gap 1, and that it is possible to optimize
over the program at the rth level in time nO(r) .
Many known linear (semidefinite) programs can be captured by constant many levels of the Sherali-
Adams (Lasserre) hierarchy. In fact, these semidefinite programs can also be captured by a “mixed”
hierarchy, first studied by Raghavendra2 [22]; where we augment the basic semidefinite relaxation by
adding new real variables and imposing linear constraints according to the Sherali-Adams hierarchy. We
will refer to this hierarchy of programs as the Sherali-Adams SDP hierarchy.
Fernandez de la Vega and Kenyon-Mathieu [14] have provided a PTAS for MAX-CUT in dense
graphs using Sherali-Adams LP hierarchy. In [20] it is shown how to get a Sherali-Adams based PTAS for
Vertex-Cover and Max-Independent-Set in minor-free graphs, while recently Mathieu and Sinclair [21]
showed that the integrality gap for the matching polytope is asymptotically 1 + 1/r, and Bateni, Charikar
and Guruswami [6] that the integrality gap for a natural LP formulation of the MaxMin allocation
problem is at most n1/r , both after r many Sherali-Adams tightenings. Chlamtac [10] and Chlamtac
and Singh [11] gave an approximation algorithm for Max-Independent-Set in hypergraphs based on
the Lasserre hierarchy, with the performance depending on the number of levels. Recently, an O(n1/4 )
approximation for Densest k-Subgraph was shown by Bhaskara et al. [7], using linear programs implied
by O(log n) levels of the Lovász-Schrijver hierarchy.
Lower bounds in these hierarchies amount to showing that the integrality gap remains large even after
many levels of the hierarchy. Integrality gaps for Ω(n) levels can be seen as unconditional lower bounds
(as they rule out even exponential time algorithms obtained by the hierarchy) in a restricted (but still fairly
interesting) model of computation. Considerable effort has been invested in proving such lower bounds
(see [3, 31, 30, 28, 8, 13, 1, 2, 27, 15, 14]). For some CSPs in particular, strong lower bounds (Ω(n)
levels) have recently been proved for the Lasserre hierarchy (which is the strongest) by [26] and [32],
2 The hierarchies studied by Raghavendra were in fact slightly weaker than the ones defined here.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 271
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
who showed a factor 2 integrality gap for MAX k-XOR and factor 2k /(2k) integrality gap for MAX k-CSP
respectively.
In a beautiful result, Raghavendra [22] showed a general connection between integrality gaps and
UG-hardness results. His result essentially shows that for MAX k-CSPq (P), if the integrality gap of a
program obtained by k levels of the Sherali-Adams SDP hierarchy is I, then the MAX k-CSPq (P) is
UG-hard to approximate better than a factor of I. However, in our case the hardness is already known
(by the work of Austrin and Mossel), and we are interested in finding the integrality gap for programs
obtained by Ω(n) levels.
Our result and techniques
Both the known results in the Lasserre hierarchy (and previous analogues in the Lovász-Schrijver
hierarchy) seemed to heavily rely on the structure of the predicate for which the integrality gap was
proved; in particular, the predicate is always some system of linear equations. It was not clear if the
techniques could be extended using only the fact that the predicate is promising (which is a much weaker
condition). In this paper, we try to explore this issue, proving Ω(n) level gaps for the Sherali-Adams SDP
hierarchy for any promising predicate.
Theorem 1.1. Let P : [q]k → {0, 1} be a predicate such that P−1 (1) contains the support of a balanced
pairwise independent distribution µ. Then for every constant ζ > 0, there exist c = c(q, k, ζ ) > 0 such
that for large enough n, the integrality gap of MAX k-CSPq (P) for the tightening obtained by cn levels of
the Sherali-Adams SDP hierarchy3 is at least
qk
−ζ .
|P−1 (1)|
Remark 1.2. We note that weaker integrality gaps for these predicates also follow, via reductions, from
the corresponding integrality gap results for Unique Games. In particular, a (log log n)Ω(1) -level gap for
the SDP hierarchy discussed above, follows from the recent results of Raghavendra and Steurer [23].
Also, Ω(nδ )-level gaps (where δ → 0 as ζ → 0) for the Sherali-Adams LP hierarchy can be deduced
from the results of Charikar, Makarychev, and Makarychev [9].
A first step in achieving our result is to reduce the problem of a level-t gap to a question about
a family of distributions over assignments associated with sets of variables of size at most t. These
distributions should be (a) supported only on satisfying (partial) assignments, (b) should be consistent
among themselves, in the sense that for S1 ⊆ S2 which are subsets of variables, the distributions over S1
and S2 should be equal on S1 , and (c) should be balanced and pairwise-independent. The first requirement
guarantees that the solution achieves objective value that corresponds to satisfying all the constraints of
the instance. The second requirement implies feasibility for the Sherali-Adams LP constraints, while the
last one makes it easy to produce vectors satisfying the semidefinite constraints.
The second step is to come up with these distributions! We explain why the simple method of picking
a uniform distribution (or a reweighting of it according to the pairwise independent distribution that is
supported by P) over the satisfying assignments cannot work. Instead we introduce the notion of “advice
3 See the resulting SDP in Section 2.3.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 272
SDP G APS FROM PAIRWISE I NDEPENDENCE
sets.” These are sets on which it is “safe” to define such simple distributions. The actual distribution for a
set S we use is then the one induced on S by a simple distribution defined on the advice-set of S. Getting
such advice sets heavily relies on notions of expansion of the constraints graph. In particular, we use the
fact that random instances have inherently good expansion properties. At the same time, such instances
are highly unsatisfiable, ensuring that the resulting integrality gap is large.
Arguing that it is indeed “safe” to use simple distributions over the advice sets relies on the fact that
the predicate P in question is promising, namely P−1 (1) contains the support of a balanced pairwise
independent distribution. We find it interesting and somewhat curious that the condition of pairwise
independence comes up in this context for a reason very different than in the case of UG-hardness. Here,
it represents the limit to which the expansion properties of a random CSP instance can be pushed to define
such distributions.
2 Preliminaries and notation
2.1 Constraint satisfaction problems
For an instance Φ of MAX k-CSPq , we denote the variables by {x1 , . . . , xn }, their domain {0, . . . , q − 1}
by [q], and the constraints by C1 , . . . ,Cm . Each constraint is a function of the form Ci : [q]Ti → {0, 1}
depending only on the values of the variables in the ordered tuple Ti with |Ti | ≤ k.
For a set S ⊆ [n] of variables, we denote by [q]S the set of all mappings from the set S to [q]. In
the context of variables, these mappings can be understood as partial assignments to a given subset of
variables. For α ∈ [q]S , we denote its projection to S0 ⊆ S by α(S0 ). Also, for α1 ∈ [q]S1 , α2 ∈ [q]S2 such
that S1 ∩ S2 = 0,
/ we denote by α1 ◦ α2 the assignment over S1 ∪ S2 defined by α1 and α2 .
We shall prove results for constraint satisfaction problems where every constraint is specified by
the same Boolean predicate P : [q]k → {0, 1}. We denote the set of assignments for which the predicate
evaluates to 1 by P−1 (1). A CSP instance for such a problem is a collection of constraints of the form of
P applied to k-tuples of literals. For a variable x with domain [q], we take a literal to be (x + a) mod q for
any a ∈ [q]. We record this more formally in the following definition.
Definition 2.1. For a given P : [q]k → {0, 1}, an instance Φ of MAX k-CSPq (P) is a set of constraints
C1 , . . . ,Cm where each constraint Ci is over a k-tuple Ti = {xi1 , . . . , xik } of variables and is of the form
P(xi1 + ai1 , . . . , xik + aik ) for some ai1 , . . . , aik ∈ [q]. We denote the maximum number of constraints that
can be simultaneously satisfied by OPT(Φ).
2.2 Expanding CSP instances
For an instance Φ of MAX k-CSPq , define its constraint graph GΦ as the following bipartite graph from
L to R. The left hand side L consists of a vertex for each constraint Ci . The right hand side R consists
of a vertex for each variable x j . There is an edge between a constraint-vertex i and a variable-vertex j,
whenever variable x j appears in constraint Ci . When Φ is clear from the context, we will abbreviate GΦ
by G.
For Ci ∈ L we denote by Γ(Ci ) ⊆ R the set of neighbors of Ci in R. For a set C ⊆ L of constraints,
Γ(C) denotes Ci ∈C Γ(Ci ). For S ⊆ R, we call a constraint, Ci ∈ L, S-dominated if Γ(Ci ) ⊆ S. We denote
S
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 273
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
m
maximize ∑ ∑ T Ci (α)·X(Ti ,α)
i=1 α∈[q] i
subject to v(i1 , j1 ) , v(i2 , j2 ) = X({i1 ,i2 },( j1 , j2 )) ∀i1 6= i2 ∈ [n], j1 , j2 ∈ [q]
v(i, j1 ) , v(i, j2 ) = 0 ∀i ∈ [n], j1 6= j2 ∈ [q]
2
v(i, j) = v(i, j) , v0 = X({i}, j) ∀i ∈ [n], j ∈ [q]
2
kv0 k = X(0,/ 0)
/ = 1
∑ X(S∪{i},α◦ j) = X(S,α) / S, α ∈ [q]S
∀S s. t. |S| < t, ∀i ∈
j∈[q]
X(S,α) ≥ 0 ∀S s. t. |S| ≤ t, ∀α ∈ [q]S
Figure 1: SDP for MAX k-CSPq augmented with level-t Sherali-Adams constraints
by G|−S the bipartite subgraph of G that we get after removing S and all S-dominated constraints. Finally,
we also denote by C(S) the set of all S-dominated constraints. Similarly, for u ∈ R we denote by Γ(u) ⊆ L
the set of neighbors of u in L.
Our result relies on the expansion of the support sets of the constraints. We make this notion formal
below.
Definition 2.2. Consider a bipartite graph G = (V, E) with partition L, R. The boundary expansion of
X ⊂ L is the value |∂ X|/|X|, where ∂ X = {u ∈ R : |Γ(u) ∩ X| = 1}. G is (r, e)-boundary expanding if the
boundary expansion for all (nonempty) subsets of L of size at most r is at least e.
2.3 The Sherali-Adams SDP hierarchy
Below we present a relaxation for the MAX k-CSPq problem as it is obtained by applying a level-t
Sherali-Adams tightening to the basic SDP formulation of some instance Φ of MAX k-CSPq . A well
known fact states that the level-n Sherali-Adams tightening (even starting from a linear program) provides
a perfect formulation, i. e., the integrality gap is 1 (see [29] or [18] for a proof).
The intuition behind the level-t Sherali-Adams tightening is the following. Note that an integer
solution to the problem can be given by a single mapping α0 ∈ [q][n] , which is an assignment to all the
variables. Using this, we can define 0/1 variables X(S,α) for each S ⊆ [n] such that |S| ≤ t and α ∈ [q]S .
The intended solution is X(S,α) = 1 if α0 (S) = α and 0 otherwise. We introduce X(0,/ 0)
/ which is intended
to be 1. By relaxing the integrality constraint on the variables, we obtain the LP conditions given by
level-t of the Sherali-Adams hierarchy.
We can further strengthen the integer program by adding the quadratic constraints
X({i1 ,i2 },( j1 , j2 )) = X({i1 }, j1 ) · X({i2 }, j2 )
for i1 , i2 ∈ [n] and j1 , j2 ∈ [q].4 As solving quadratic programs is NP-hard we then relax these quadratic
4 Abusing notation slightly, here we use X
({i1 ,i2 },( j1 , j2 )) to denote X({i1 ,i2 },α) where α is the function mapping i1 to j1 and i2
to j2 .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 274
SDP G APS FROM PAIRWISE I NDEPENDENCE
constraints to the existence of vectors v(i, j) and a unit vector v0 , for which we require that
v(i1 , j1 ) , v(i2 , j2 ) = X({i1 ,i2 },( j1 , j2 )) and v(i, j) , v0 = X({i}, j) .
The complete relaxation can be seen in Figure 1.
For an SDP formulation of MAX k-CSPq , and for a given instance Φ of the problem, we denote
by FRAC(Φ) the SDP (fractional) optimum, and by OPT(Φ) the integral optimum. For the particu-
lar instance Φ, the integrality gap is then defined as FRAC(Φ)/OPT(Φ). The integrality gap of the
formulation is the supremum of integrality gaps over all instances.
Next we give a sufficient condition for the existence of a solution to the program obtained by level-t
of the Sherali-Adams SDP hierarchy for a MAX k-CSPq instance Φ.
Lemma 2.3. Consider a family {D(S)}S⊆[n]:|S|≤t of distributions, where each D(S) is defined over [q]S .
Suppose that for every S ⊆ T ⊆ [n] with |T | ≤ t, the distributions D(S), D(T ) are equal on S and there
exists a set v(i, j) i∈[n], j∈[q] of vectors and a unit vector v0 satisfying:
1. for all i ∈ [n] and j1 6= j2 , v(i, j1 ) , v(i, j2 ) = 0,
2
2. for all i ∈ [n], j ∈ [q], v(i, j) , v0 = v(i, j) = PrD({i}) [ j], and
3. for all i1 6= i2 ∈ [n] and j1 , j2 ∈ [q], v(i1 , j1 ) , v(i2 , j2 ) = PrD({i1 ,i2 }) [( j1 , j2 )].
Then the vectors together with the LP variables X(S,α) = PrD(S) [α] form a feasible solution to the program
in Figure 1.
Proof. Consider some S ⊆ [n], |S| < t, and some i 6∈ S. Note that the distributions D(S), D(S ∪ {i}) are
equal on S, and therefore we have
∑ X(S∪{i},α◦ j) = ∑ Prβ ∼D(S∪{i}) [β = α ◦ j]
j∈[q] j∈[q]
= ∑ Prβ ∼D(S∪{i}) [(β (i) = j) ∧ (β (S) = α)]
j∈[q]
= Prβ ∼D(S∪{i}) [β (S) = α]
= Prβ 0 ∼D(S) [β 0 = α]
= X(S,α) .
The same argument for S = 0/ shows that X(0,/ 0)
/ = 1. It is clear that the solution satisfies all the other
required conditions by definition, which proves the lemma.
2.4 Pairwise independence and approximation resistant predicates
We say that a distribution µ over variables x1 , . . . , xk , is a balanced pairwise independent distribution over
[q]k , if we have
1 1
∀ j ∈ [q].∀i. Prµ [xi = j] = and ∀ j1 , j2 ∈ [q].∀i1 6= i2 . Prµ [(xi1 = j1 ) ∧ (xi2 = j2 )] = .
q q2
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 275
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
A predicate P is called approximation resistant if it is hard to approximate the MAX k-CSPq (P) problem
better than using a random assignment. Assuming the Unique Games Conjecture, Austrin and Mossel [5]
show that a predicate is approximation resistant if it is possible to define a balanced pairwise independent
distribution µ such that P is always 1 on the support of µ.
Definition 2.4. A predicate P : [q]k → {0, 1} is called promising if there exist a distribution supported
over a subset of P−1 (1) that is pairwise independent and balanced. If µ is such a distribution we say that
P is promising supported by µ.
3 Towards defining consistent distributions
To construct valid solutions for the Sherali-Adams SDP hierarchy, we need to define distributions over
every set S of bounded size as is required by Lemma 2.3. Since we will deal with promising predicates
supported by some distribution µ, in order to satisfy consistency between distributions we will heavily
rely on the fact that µ is a balanced pairwise independent distribution.
Assume for simplicity that µ is uniform over P−1 (1) (the intuition for the general case is not
significantly different). It is instructive to think of q = 2 and the predicate P being k-XOR, k ≥ 3. Observe
that the uniform distribution over P−1 (1) is pairwise independent and balanced. A first attempt would be
to define for every S, the distribution D(S) as the uniform distribution over all consistent assignments of
S. We argue that such distributions are in general problematic. This follows from the fact that satisfying
assignments are not always extendible. Indeed, consider two constraints Ci1 ,Ci2 ∈ L that share a common
variable j ∈ R. Set S2 = Ti1 ∪ Ti2 , and S1 = S2 \ { j}.5 Assuming that the support of no other constraint
is contained in S2 , we get that distribution D(S1 ) maps any variable in S1 to {0, 1} with probability 1/2
independently, but some of these assignments are not even extendible to S2 meaning that D(S2 ) will
assign them with probability zero.
Thus, to define D(S), we cannot simply sample assignments satisfying all constraints in C(S) with
probabilities given by µ. In fact the above example shows that any attempt to blindly assign a set S with
a distribution that is supported on all satisfying assignments for S is bound to fail. At the same time it
seems hard to reason about a distribution that uses a totally different concept. To overcome this obstacle,
we take a two step approach:
1. For a set S we define a superset S such that S is “global enough” to contain sufficient information,
while it also is “local enough” so that C(S) is not too large. We require the property of such sets
that if we remove S and C(S), then the remaining graph G|−S still has good expansion. We deal
with this in Section 3.1.
2. When µ is the uniform distribution over P−1 (1), the distribution D(S) is going to be the uniform
distribution over satisfying assignments in S. In the case that µ is not uniform over P−1 (1), we
give a natural generalization to the above uniformity. We show how to define distributions, which
we denote by Pµ (S), such that for S1 ⊆ S2 , the distributions Pµ (S1 ) and Pµ (S2 ) are guaranteed to
be consistent if G|−S1 has good expansion. This appears in Section 3.2.
We then combine the two techniques and define D(S) according to Pµ (S). This is done in Section 4.
5 Remember that T is the set of variables appearing in C and T is the set of variables appearing in C .
i1 i1 i2 i2
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 276
SDP G APS FROM PAIRWISE I NDEPENDENCE
3.1 Finding advice-sets
We now give an algorithm below to obtain a superset S for a given set S, which we call the advice-set of
S. It is inspired by the “expansion correction” procedure in [8].
Algorithm Advice
The input is an (r, e1 )-boundary expanding bipartite graph G = (L, R, E), some e2 ∈ (0, e1 ), and some
S ⊆ R, |S| < (e1 − e2 )r, with some order S = {x1 , . . . , xt }.
Initially set S ← 0/ and ξ ← r
For j = 1, . . . , |S| do
M j ← 0/
S ← S ∪ {x j }
If G|−S is not (ξ , e2 )-boundary expanding then
Find a maximal M j ⊂ L in G|−S , such that |M j | ≤ ξ and |∂ M j | ≤ e2 |M j | in G|−S
S ← S ∪ Γ(M j )
ξ ← ξ − |M j |
Return S
Theorem 3.1. Algorithm Advice, when ran with inputs G, e1 , e2 , r, and S, returns S ⊆ R such that
(a) G|−S is (ξS , e2 )-boundary expanding,
|S|
(b) ξS ≥ r − , and
e1 − e2
(2e1 + k − e2 )|S|
(c) |S| ≤ .
2(e1 − e2 )
Proof. Let ξS be the value of ξ when the loop terminates. From the bounded size of M j and how ξ
changes at each iteration we know that ξ remains non-negative throughout the execution of the while
loop, and in particular ξS ≥ 0. Note that at step j, all the neighbors of M j are added to the set S so no
member of M j will be in G−S after the jth step. In particular, all the sets M j will be disjoint.
In order to prove (a) we will prove the following loop invariant: G|−S is (ξ , e2 )-boundary expanding.
Indeed, note that the input graph G is (ξ , e1 )-boundary expanding so the invariant holds at the beginning.
At step j consider the set S ∪ {x j }, and suppose that G−(S∪{x j }) is not (ξ , e2 )-boundary expanding. We
find maximal M j , |M j | ≤ ξ , such that |∂ M j | ≤ e2 |M j |. We claim that G−(S∪{x j }∪Γ(M j )) is (ξ − |M j |, e2 )-
boundary expanding. Assuming the contrary, there must be M 0 ⊂ L such that |M 0 | ≤ ξ − |M j | and
|∂ M 0 | ≤ e2 |M 0 |. As we mentioned above, M j will be disjoint from the left vertices of G−(S∪{x j }∪Γ(M j )) ,
and in particular it will be disjoint from M 0 . Consider then M j ∪ M 0 and note that |M j ∪ M 0 | ≤ ξ .
More importantly (right before we added Γ(M j ) to S) |∂ (M j ∪ M 0 )| ≤ e2 |M j | + e2 |M 0 | = e2 |M j ∪ M 0 |
contradicting the maximality of M j ; (a) follows.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 277
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
To show (b) we consider the set M = tj=1 M j and upperbound and lowerbound its boundary expansion
S
in G in two different ways. Notice that as we mentioned M j ’s are disjoint, so |M| = ∑tj=1 |M j | = r − ξS .
Since G is (r, e1 )-boundary expanding, the set M has at least e1 (r − ξS ) boundary neighbors in G. But
each member of ∂ M\S is in the boundary of exactly one of the M j ’s, so it will be counted towards
the boundary expansion of M j in G−S in the j iteration of the loop (for some j). Given that M j ’s have
boundary expansion at most e2 we have
e1 (r − ξS ) ≤ |∂ M| ≤ |S| + ∑ e2 |M j | = |S| + e2 (r − ξS ) ,
j
which readily implies (b).
Finally note that S consists of S union the neighbors of all M j ’s. But given that M j ’s have boundary at
most expansion e2 they can not have a big neighbor set. In particular
e2 + k (e2 + k)|S| (2e1 + k − e2 )|S|
|S| ≤ |S| + ∑ Γ(M j ) ≤ |S| + ∑ |M j | ≤ |S| + = ,
j 2 j 2(e1 − e2 ) 2(e1 − e2 )
which proves (c).
3.2 Defining the Distributions Pµ (S)
We now define for every set S, a distribution Pµ (S) such that for any α ∈ [q]S , PrPµ (S) [α] > 0 only if α
satisfies all the constraints in C(S). For a constraint Ci with set of inputs Ti , defined as Ci (xi1 , . . . , xik ) ≡
P(xi1 + ai1 , . . . , xik + aik ), let µi : [q]Ti → [0, 1] denote the distribution
µi (xi1 , . . . , xik ) = µ(xi1 + ai1 , . . . , xik + aik )
so that the support of µi is contained in Ci−1 (1). We then define the distribution Pµ (S) by picking each
assignment α ∈ [q]S with probability proportional to ∏Ci ∈C(S) µi (α(Ti )). Formally,
1
PrPµ (S) [α] = · ∏ µi (α(Ti )) (3.1)
ZS C ∈C(S)
i
where α(Ti ) is the restriction of α to Ti and ZS is a normalization factor given by
ZS = ∑ ∏ µi (α(Ti )) .
α∈[q]S Ci ∈C(S)
To understand the distribution, it is easier to think of the special case when µ is just the uniform
distribution on P−1 (1) (like in the case of MAX k-XOR). Then Pµ (S) is simply the uniform distribution
on assignments satisfying all the constraints in C(S). When µ is not uniform, the probabilities are
weighted by the product of the values µi (α(Ti )) for all the constraints.6 However, we still have the
property that if PrPµ (S) [α] > 0, then α satisfies all the constraints in C(S).
In order for the distribution Pµ (S) to be well defined, we need to ensure that ZS > 0. The following
lemma shows how to calculate ZS if G is sufficiently expanding, and simultaneously proves that if S1 ⊆ S2 ,
and if G|−S1 is sufficiently expanding, then Pµ (S1 ) is consistent with Pµ (S2 ) over S1 .
6 Note however that P
µ (S) is not a product distribution because different constraints in C(S) may share variables.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 278
SDP G APS FROM PAIRWISE I NDEPENDENCE
Lemma 3.2. Let Φ be a MAX k-CSPq (P) instance as above and S1 ⊆ S2 be two sets of variables such
that both G and G|−S1 are (r, k − 3 + δ )-boundary expanding for some δ > 0 and |C(S2 )| ≤ r. Then
ZS2 = q|S2 | /qk|C(S2 )| , and for any α1 ∈ [q]S1
∑ PrPµ (S2 ) [α2 ] = PrPµ (S1 ) [α1 ] . (3.2)
α2 ∈[q]S2
α2 (S1 )=α1
Proof. Let C = C(S2 ) \ C(S1 ) be the set of t constraints dominated by S2 but not S1 . Without loss of
generality let C = {C1 , . . . ,Ct } with Ci being on the set of variables Ti some of which might be set by α1 .
Note that any α2 consistent with α1 can be written as α1 ◦ α for some α ∈ [q]S2 \S1 . We will show a way
to calculate a sum similar to the left hand side of (3.2). Note that these calculations are meaningful even
if ZS1 or ZS2 are zero, in which case both sides are simply zero. Taking S1 = 0/ will then give us the value
of ZS2 .
ZS2 · ∑ PrPµ (S2 ) [α2 ] = ∑ ∏ µi ((α1 ◦ α)(Ti ))
α2 ∈[q]S2 α∈[q]S2 \S1 Ci ∈C(S2 )
α2 (S1 )=α1
!
t
= ∏ µi (α1 (Ti )) ∑ ∏ µ j ((α1 ◦ α)(Tj ))
Ci ∈C(S1 ) α∈[q]S2 \S1 j=1
t
= ZS1 · PrPµ (S1 ) [α1 ] ∑ ∏ µ j ((α1 ◦ α)(Tj )) .
α∈[q]S2 \S1 j=1
The following claim lets us calculate this last sum conveniently using the expansion of G|−S1 .
Claim 3.3. Let C be as above. Then there exists an ordering Ci1 , . . . ,Cit of constraints in C and a partition
of S2 \ S1 into sets of variables F1 , . . . , Ft and Ft+1 such that for all j ≤ t, Fj ⊆ Ti j , |Fj | ≥ k − 2, and
\
∀ j Fj ∪`> j Ti` = 0/ .
Proof of Claim 3.3. We build the sets Fj inductively using the fact that G|−S1 is (r, k − 3 + δ )-boundary
expanding.
Start with the set of constraints C1 = C. Since |C1 | = |C(S2 ) \ C(S1 )| ≤ r, C1 should be expanding in
G−S1 , i. e., |∂ (C1 ) \ S1 | ≥ (k − 3 + δ )|C1 |. Hence, there exists C j ∈ C1 contributing at least k − 2 variables
to the boundary of C1 , i. e., |T j ∩ (∂ (C1 ) \ S1 )| ≥ k − 2. Let T j ∩ (∂ (C1 ) \ S1 ) = F1 and i1 = j. We then
take C2 = C1 \ {Ci1 } and continue in the same way. What is left from S2 \ S1 after the last step will be
Ft+1 . It is not hard to check that Ft+1 is the portion of S2 \ S1 that is not in any Ci although we will not
use this.
Since at every step we have Fj ⊆ ∂ (C j ) \ S1 and, for all ` > j, C` ⊆ C j , Fj shares no variables with
Γ(Cl ) for ` > j. Hence, we get Fj ∩ ∪`> j Ti` = 0/ as claimed.
Using this decomposition, we can reorder the sum and split it as
t
∑ ∏ µ j (α1 ◦ α(Tj )) = ∑ ∑ µi ∑ t µit−1 · · · ∑ µi ∑ µi 2 1
α∈[q]S2 \S1 j=1 βt+1 ∈[q]Ft+1 βt ∈[q]Ft βt ∈[q]Ft−1 β2 ∈[q]F2 β1 ∈[q]F1
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 279
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
where the input to each µi j depends on α1 and β j , . . . , βt+1 but not on β1 , . . . , β j−1 .
We now reduce the expression from right to left. Since F1 contains at least k − 2 variables and µi1 is a
balanced pairwise independent distribution,
1
∑ µi = Prµ [(α1 ◦ β2 . . . ◦ βt )(Ti \ F1 )] = qk−|F |
1 1
1
β1 ∈[q]F1
irrespective of the values assigned by α1 ◦ β2 ◦ · · · ◦ βt to the remaining (at most 2) variables in Ti1 \ F1 .
Continuing in this fashion from right to left, we get that
t
1
∑ ∏ µi ((α1 ◦ α)(Ti )) = = q|S2 \S1 |−k|C(S2 )\C(S1 )| .
j j
kt−∑t+1
j=1 |Fj |
α∈[q]S2 \S1 j=1 q
Hence, we get that
!
q|S2 \S1 |
ZS2 · ∑ PrPµ (S2 ) [α2 ] = ZS1 · PrPµ (S1 ) [α1 ] . (3.3)
α2 ∈[q]S2
qk|C(S2 )\C(S1 )|
α2 (S1 )=α1
Now, since we know that G is (r, k − 3 + δ )-boundary expanding, we can replace S1 by 0/ in the above
calculation to get
ZS2 = ∑ ∏ µi ((α1 ◦ α)(Ti )) = q|S2 |−k|C(S2 )| ,
α∈[q]S2 Ci ∈C(S2 )
as we wanted. Plugging in the value of ZS2 and ZS1 into (3.3) will show that
∑ PrPµ (S2 ) [α2 ] = PrPµ (S1 ) [α1 ] ,
α2 ∈[q]S2
α2 (S1 )=α1
which proves the lemma.
We are now almost ready to describe our Sherali-Adams SDP solution. The only other property of
Pµ (S) that we need to show is that it is pairwise-independent and balanced.
Claim 3.4. Let G be a (r, k − 3 + ε)-boundary expanding constraint graph, with ε > 2/3 in which no
two constraints share more than one variable. Then for any S ⊂ R, |S| ≤ r, the distribution Pµ (S) is a
pairwise-independent and balanced distribution. That is, for all i1 , i2 ∈ S, j1 , j2 ∈ [q],
Prα∼Pµ (S) [αi1 = j1 ] = 1/q , Prα∼Pµ (S) [(αi1 = j1 ) ∧ (αi2 = j2 )] = 1/q2 .
Proof. Let S be a subset of the variables, i, j ∈ S and ε 0 = min(1, ε − 2/3). We will first show that G−{i, j}
is (r, k − 3 + ε 0 )-boundary expanding.
Let C be a set of constraints with |C| ≤ r. When |C| = 1, C has k boundary neighbors in G and hence
at least k − 2 ≥ (k − 3 + ε 0 )|C| boundary neighbors in G|−{i, j} . When |C| = 2, the number of boundary
neighbors in G must be at least 2k − 2 since the two constraints in C can share at most one variable. It
follows that |∂ C| is at least 2k − 2 − 2 ≥ (k − 3 + ε 0 )|C| in G|−{i, j} .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 280
SDP G APS FROM PAIRWISE I NDEPENDENCE
Finally, when 3 ≤ |C| ≤ r, we get that the size of |∂ C| in G|−{i, j} is at least (k − 3 + ε)|C| − 2 as G is
(r, k − 3 + ε)-boundary expanding. This proves the claim as
(k − 3 + ε)|C| − 2 = (k − 3 + ε − 2/|C|)|C| ≥ (k − 3 + ε 0 )|C| .
It follows from applying Lemma 3.3 with S2 = S and S1 = {i, j} that Pµ (S) agrees with Pµ ({i, j})
on the set {i, j}. Now note that for k = 2 the only promising predicate is the one accepting everything
for which the theorem is trivial, so one can assume that k > 2 and C({i, j}) is empty. It follows that
Pµ ({i, j}) is the uniform distribution on [q]{i, j} which completes the proof.
4 Constructing the integrality gap
We now show how to construct integrality gaps using the ideas in the previous section. For a given
promising predicate P, our integrality gap instance will be a random instance Φ of the MAX k-CSPq (P)
problem, conditioned on no two constraints sharing more than one variable. To generate a random
instance with m constraints, for every constraint Ci , we randomly select a k-tuple Ti = {xi1 , . . . , xik } of
distinct variables and ai1 , . . . , aik ∈ [q], and put Ci ≡ P(xi1 + ai1 , . . . , xik + aik ). It is well known and used
in various works on integrality gaps and proof complexity (e. g., [8], [1, 2], [27] and [26]), that random
instances of CSPs are both highly unsatisfiable and highly expanding. We capture the properties we need
in the lemma below. The proof uses standard arguments; we defer it to the next section.
Lemma 4.1. Let ε, δ > 0 and a predicate P : [q]k → {0, 1} be given. Then there exist γ = O(qk log q/ε 2 ),
η = Ω((1/γ)10/δ ) and N ∈ N, such that if n ≥ N and Φ is a random instance of MAX k-CSPq (P) with
m = γn constraints, then with probability exp(−O(k4 γ 2 ))
|P−1 (1)|
1. OPT(Φ) ≤ (1 + ε) · m,
qk
2. for any set C of constraints with |C| ≤ ηn, we have |∂ (C)| ≥ (k − 2 − δ )|C|, and
3. no two constraints in Φ share more than one variable.
Let Φ be an instance of MAX k-CSPq on n variables for which GΦ is (ηn, k − 2 − δ )-boundary
expanding for some δ < 1/4, as in Lemma 4.1. For such a Φ, we now define the distributions D(S). In
the rest of this chapter we assume k ≥ 3 as for k = 2 the only promising predicate is the one satisfying all
assignments for which the theorem is trivial.
For a set S of size at most t = ηn/6k, let S be subset of variables output by the algorithm Advice
when run with input S and parameters r = ηn, e1 = (k − 2 − δ ), e2 = (k − 8/3 − δ ) on the graph GΦ .
Theorem 3.1 shows that
(2k − 4 − 2δ + k − k + 8/3 + δ )|S| (6k − 4 − 3δ )|S| ηn
|S| ≤ = ≤ ,
4/3 4 4
and, also,
|S| ηn 3ηn
ξS ≥ ηn − = ηn − > .
2/3 4k 4
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 281
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
We then use (3.1) to define the distribution D(S) for sets S of size at most ηn/6k as
PrD(S) [α] = ∑ PrP (S) [β ] .
µ
β ∈[q]S
β (S)=α
Using the properties of the distributions Pµ (S), we can now prove that the distributions D(S) are
consistent.
Claim 4.2. Let the distributions D(S) be defined as above. Then for any two sets S1 ⊆ S2 ⊆ [n] with
|S2 | ≤ t = ηn/6k, the distributions D(S1 ), D(S2 ) are equal on S1 .
Proof. The distributions D(S1 ) and D(S2 ) are defined according to Pµ (S1 ) and Pµ (S2 ), respectively. To
prove the claim, we show that Pµ (S1 ) and Pµ (S2 ) are equal to the distribution Pµ (S1 ∪ S2 ) on S1 and S2 ,
respectively (note that it need not be the case that S1 ⊆ S2 ).
Let S3 = S1 ∪ S2 . Since |S1 |, |S2 | ≤ ηn/4, we have |S3 | ≤ ηn/2. We will first show that |C(S3 )| ≤
3ηn/4. Assume to the contrary, and let C be any subset of C(S3 ) of size 3ηn/4. Given that k ≥ 3 and
δ < 1/4 we would have the following bound on the boundary of C,
|∂ C| |Γ(C)| |S3 | 1/2 2
≤ ≤ ≤ = < k−2−δ ,
|C| |C| |C| 3/4 3
which would contradict boundary expansion of G.
Now, by Theorem 3.1, we know that both G|−S1 and G|−S2 are (3ηn/4, k − 8/3 − δ )-boundary
expanding. Thus, using Lemma 3.2 for the pairs S1 ⊆ S3 and S2 ⊆ S3 , we get that
PrD(S1 ) [α1 ] = ∑ PrPµ (S1 ) [β1 ] = ∑ PrPµ (S3 ) [β3 ]
β1 ∈[q]S1 β3 ∈[q]S3
β1 (S1 )=α1 β3 (S1 )=α1
= ∑ PrPµ (S2 ) [β2 ] = ∑ PrD(S2 ) [α2 ]
β2 ∈[q]S2 α2 ∈[q]S2
β2 (S1 )=α1 α2 (S1 )=α1
which shows that D(S1 ) and D(S2 ) are equal on S1 .
It is now easy to prove the main result.
Theorem 4.3. Let P : [q]k → {0, 1} be a promising predicate. Then for every constant ζ > 0, there exist
c = c(q, k, ζ ), such that for large enough n, the integrality gap of MAX k-CSPq (P) for the program
obtained by cn levels of the Sherali-Adams SDP hierarchy is at least
qk
−ζ .
|P−1 (1)|
Proof. We take ε = ζ /qk , δ = 1/4 and consider a random instance Φ of MAX k-CSPq (P) with m = γn
−1
as given by Lemma 4.1. Thus, OPT(Φ) ≤ |P qk(1)| (1 + ε) · m.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 282
SDP G APS FROM PAIRWISE I NDEPENDENCE
On the other hand, by Claim 4.2 we can define distributions D(S) over every set of at most ηn/6k
variables such that for S1 ⊆ S2 , D(S1 ) and D(S2 ) are consistent over S1 . Also, Claim 3.4 implies that
Pµ (S) hence D(S) is pairwise-independent and balanced for any S. We can now construct the SDP
vectors with inner products agreeing with the probabilities according to the distributions D(S) = Pµ (S)
for an instance satisfying the above property using the following simple fact.
Claim 4.4. There exist vectors {v(i, j) }i∈[n], j∈[q] and v0 satisfying:
1. for all i ∈ [n] and j1 6= j2 , v(i, j1 ) , v(i, j2 ) = 0,
2
2. for all i ∈ [n], j ∈ [q], v(i, j) , v0 = v(i, j) = 1/q, and
3. for all i1 6= i2 ∈ [n] and j1 , j2 ∈ [q], v(i1 , j1 ) , v(i2 , j2 ) = 1/q2 .
Proof. Let e1 , . . . , en be an orthonormal basis for Rn and u0 , . . . , uq−1 be vertices of a q − 1 dimensional
simplex satisfying u j1 , u j2 = −1/(q − 1) when j1 6= j2 and 1 otherwise. Let v0 ∈ Rn(q−1)+1 be a unit
vector such that v0 , ei ⊗ u j = 0 for all i ∈ [n] and j ∈ [q]. We then define v(i, j) as
√
1 q−1
v(i, j) := v0 + (ei ⊗ u j ) .
q q
It is easy to check that v0 , v(i1 , j1 ) = 1/q and v(i1 , j1 ) , v(i2 , j2 ) = 1/q2 for all i1 6= i2 ∈ [n] and j1 , j2 ∈ [q].
Also, for j1 6= j2
1 q−1 −1
v(i, j1 ) , v(i, j2 ) = 2 + 2 · = 0
q q q−1
which proves the claim.
By Lemma 2.3 this gives a feasible solution to the SDP obtained by ηn/(6k) levels. Also, by
definition of D(S), we have that PrD(S) [α] > 0 only if α satisfies all constraints in C(S) ⊇ C(S). Hence,
the value of FRAC(Φ) is given by
m m m
∑ ∑ Ci (α)X(T ,α) = ∑ ∑ Ci (α)PrD(T ) [α] = ∑ ∑ PrD(T ) [α] = m .
i i i
i=1 α∈[q]Ti i=1 α∈[q]Ti i=1 α∈[q]Ti
Thus, the integrality gap after ηn/(6k) levels is at least
FRAC(Φ) qk qk
= −1 ≥ −1 −ζ .
OPT(Φ) |P (1)|(1 + ε) |P (1)|
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 283
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
5 Proof of Lemma 4.1
The proof is a simple modification of the proof of [27, Lemma 5]. We include it for convenience.
Proof. Let α ∈ [q]n be any fixed assignment. For a fixed α, the events that a constraint Ci is satisfied are
independent and happen with probability |P−1 (1)|/qk each. Hence, the probability over the choice of Φ
that α satisfies more than (|P−1 (1)|/qk )(1 + ε) · γn constraints is at most
ε γn|P−1 (1)|
2
exp −
3qk
by Chernoff bounds. By a union bound, the probability that any assignment satisfies more than
(|P−1 (1)|/qk )(1 + ε) · γn constraints is at most
ε γn|P−1 (1)| ε 2 γn|P−1 (1)|
2
n
q · exp − = exp n ln q −
3qk 3qk
which is o(1) for γ = (6qk ln q)/ε 2 .
For showing the boundary expansion, we note that it suffices to show that the constraints have large
expansion, i. e., each set of s constraints (for s ≤ ηn) contains at least (k − 1 − δ /2)s variables. Since
each non-boundary variable occurs in at least two constraints, we get that that the number of boundary
variables must be at least 2(k − 1 − δ /2)s − ks = (k − 2 − δ )s.
To show this, consider the probability that a set of s constraints contains at most cs variables, where
c = k − 1 − δ . This is upper bounded by
cs −s
n γn n
· k · s! · .
cs s s k
Here csn is the number of ways of choosing the cs variables involved,
(csk) is the number of ways of
s
picking s tuples out of all possible k-tuples on cs variables and s! γn s is the number of ways of selecting
s
the s constraints. The number nk is simply the number of ways of picking s of these k-tuples in an
unconstrained way. Using ( ab )b ≤ ab ≤ ( a·e b s
b ) , s! ≤ s and collecting terms, we can bound this expression
by
!δ s/2
s δ s/2 s s δ s/2 sγ 10/δ
e2k+1−δ /2 k1+δ /2 γ ≤ (γ 5 )s = .
n n n
We need to show that the probability that a set of s constraints contains less than cs variables for any
s ≤ ηn is o(1). Thus, we sum this probability over all s ≤ ηn to get
!δ s/2 !δ s/2 !δ s/2
ln2 n
ηn
sγ 10/δ sγ 10/δ ηn
sγ 10/δ
∑ = ∑ + ∑
n n n
s=1 s=1 s=ln2 n+1
γ 10 2 (δ /2) ln2 n
≤ O ln n +O η · γ 10/δ .
nδ /2
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 284
SDP G APS FROM PAIRWISE I NDEPENDENCE
The first term is o(1) and is small for large n. The second term is also o(1) for η = 1/(100γ 10/δ ).
Thus, we get the first two properties with probability 1 − o(1). Finally, the probability that there are no
two constraints sharing two variables must be at least ∏i=1,...,m (1 − O(i · k4 /n2 )) because when we choose
the ith constraint, by wanting it to not share two variables with another previously chosen constraint,
we are forbidding any of the 2k pairs of variables in the ith constraint from being equal to any of the
(i − 1) · 2k pairs in the previously chosen ones. Now using that for small enough x, 1 − x > exp(−2x),
the probability is at least
m
∑i=1 i · k4
4 2
k ·m
= exp −O k4 γ 2 .
exp −O 2
= exp −O 2
n n
Acknowledgements
The authors would like to thank the anonymous reviewers for suggestions that improved the presentation
of the paper.
References
[1] M IKHAIL A LEKHNOVICH , S ANJEEV A RORA , AND I ANNIS T OURLAKIS: Towards strong nonap-
proximability results in the Lovász-Schrijver hierarchy. In Proc. 37th STOC, pp. 294–303. ACM
Press, 2005. [doi:10.1145/1060590.1060634] 271, 281
[2] M IKHAIL A LEKHNOVICH , S ANJEEV A RORA , AND I ANNIS T OURLAKIS: Towards strong nonap-
proximability results in the Lovász-Schrijver hierarchy. Comput. Complexity, 20(4):615–648, 2011.
[doi:10.1007/s00037-011-0027-z] 271, 281
[3] S ANJEEV A RORA , B ÉLA B OLLOBÁS , L ÁSZLÓ L OVÁSZ , AND I ANNIS T OURLAKIS: Proving
integrality gaps without knowing the linear program. Theory of Computing, 2(1):19–51, 2006.
Preliminary version in FOCS’02. [doi:10.4086/toc.2006.v002a002] 271
[4] P ER AUSTRIN AND J OHAN H ÅSTAD: Randomly supported independence and resistance. SIAM J.
Comput., 40(1):1–27, 2011. Preliminary version in STOC’09. [doi:10.1137/100783534] 270
[5] P ER AUSTRIN AND E LCHANAN M OSSEL: Approximation resistant predicates from pairwise
independence. Comput. Complexity, 18(2):249–271, 2009. Preliminary version in CCC’08.
[doi:10.1007/s00037-009-0272-6] 270, 276
[6] M OHAMMAD H OSSEIN BATENI , M OSES C HARIKAR , AND V ENKATESAN G URUSWAMI: MaxMin
allocation via degree lower-bounded arborescences. In Proc. 41st STOC, pp. 543–552. ACM Press,
2009. [doi:10.1145/1536414.1536488] 271
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 285
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
[7] A DITYA B HASKARA , M OSES C HARIKAR , E DEN C HLAMTAC , U RIEL F EIGE , AND A RAVIN -
DAN V IJAYARAGHAVAN : Detecting high log-densities—an O(n1/4 ) approximation for densest
k-subgraph. In Proc. 42nd STOC, pp. 201–210. ACM Press, 2010. [doi:10.1145/1806689.1806719]
271
[8] J OSHUA B URESH -O PPENHEIM , N ICOLA G ALESI , S HLOMO H OORY, AVNER M AGEN , AND
T ONIANN P ITASSI: Rank bounds and integrality gaps for cutting planes procedures. Theory of
Computing, 2(4):65–90, 2006. Preliminary version in FOCS’03. [doi:10.4086/toc.2006.v002a004]
271, 277, 281
[9] M OSES C HARIKAR , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: Integrality
gaps for Sherali–Adams relaxations. In Proc. 41st STOC, pp. 283–292. ACM Press, 2009.
[doi:10.1145/1536414.1536455] 272
[10] E DEN C HLAMTAC: Approximation algorithms using hierarchies of semidefinite program-
ming relaxations. In Proc. 48th FOCS, pp. 691–701. IEEE Comp. Soc. Press, 2007.
[doi:10.1109/FOCS.2007.72] 271
[11] E DEN C HLAMTAC AND G YANIT S INGH: Improved approximation guarantees through higher
levels of SDP hierarchies. In Proc. 11th Internat. Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX’08), volume 5171 of Lecture Notes in Computer
Science, pp. 49–62. Springer, 2008. [doi:10.1007/978-3-540-85363-3_5] 271
[12] L ARS E NGEBRETSEN AND J ONAS H OLMERIN: More efficient queries in PCPs for NP and improved
approximation hardness of maximum CSP. Random Structures Algorithms, 33:497–514, 2008.
Preliminary version in STACS’05. [doi:10.1002/rsa.20226] 270
[13] U RIEL F EIGE AND ROBERT K RAUTHGAMER: The probable value of the Lovász-Schrijver
relaxations for maximum independent set. SIAM J. Comput., 32(2):345–370, 2003.
[doi:10.1137/S009753970240118X] 271
[14] W ENCESLAS F ERNANDEZ DE LA V EGA AND C LAIRE K ENYON -M ATHIEU: Linear programming
relaxations of maxcut. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07),
pp. 53–61. SIAM, 2007. [ACM:1283390] 271
[15] KONSTANTINOS G EORGIOU , AVNER M AGEN , T ONIANN P ITASSI , AND I ANNIS T OURLAKIS:
Integrality gaps of 2 − o(1) for Vertex Cover SDPs in the Lovász-Schrijver hierarchy. SIAM J.
Comput., 39(8):3553–3570, 2010. Preliminary version in FOCS’07. [doi:10.1137/080721479] 271
[16] V ENKATESAN G URUSWAMI AND P RASAD R AGHAVENDRA: Constraint satisfaction over a non-
Boolean domain: Approximation algorithms and Unique-Games hardness. In Proc. 11th Internat.
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’08),
pp. 77–90. Springer, 2008. [doi:10.1007/978-3-540-85363-3_7] 270
[17] J EAN B. L ASSERRE: An explicit equivalent positive semidefinite program for nonlinear 0-1
programs. SIAM J. Optim., 12(3):756–769, 2002. [doi:10.1137/S1052623400380079] 271
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 286
SDP G APS FROM PAIRWISE I NDEPENDENCE
[18] M ONIQUE L AURENT: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre
relaxations for 0-1 programming. Math. Oper. Res., 28(3):470–496, August 2003.
[doi:10.1287/moor.28.3.470.16391] 271, 274
[19] L. L OVÁSZ AND A. S CHRIJVER: Cones of matrices and set-functions and 0-1 optimization. SIAM
J. Optim., 1(2):166–190, May 1991. [doi:10.1137/0801013] 271
[20] AVNER M AGEN AND M OHAMMAD M OHARRAMI: Robust algorithms for MAX INDEPENDENT SET
on minor-free graphs based on the Sherali–Adams hierarchy. In Proc. 12th Internat. Workshop on
Approximation Algorithms for Combinatorial Optimization Problems (APPROX’09), pp. 258–271,
Berlin, Heidelberg, 2009. Springer-Verlag. [doi:10.1007/978-3-642-03685-9_20] 271
[21] C LAIRE M ATHIEU AND A LISTAIR S INCLAIR: Sherali-Adams relaxations of the matching polytope.
In Proc. 41st STOC, pp. 293–302. ACM Press, 2009. [doi:10.1145/1536414.1536456] 271
[22] P RASAD R AGHAVENDRA: Optimal algorithms and inapproximability results for every CSP? In
Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414] 271, 272
[23] P RASAD R AGHAVENDRA AND DAVID S TEURER: Integrality gaps for strong SDP relax-
ations of unique games. In Proc. 50th FOCS, pp. 575–585. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/FOCS.2009.73] 272
[24] A LEX S AMORODNITSKY AND L UCA T REVISAN: Gowers uniformity, influence of vari-
able, and PCPs. SIAM J. Comput., 39:323–360, 2009. Preliminary version in STOC’06.
[doi:10.1137/070681612] 270
[25] A LEX S AMORODNITSKY AND L UCA T REVISAN: A PCP charcaterization of NP with op-
timal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2010.
[doi:10.1145/335305.335329] 270
[26] G RANT S CHOENEBECK: Linear level Lasserre lower bounds for certain k-CSPs. In Proc. 49th
FOCS, pp. 593–602. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.74] 271, 281
[27] G RANT S CHOENEBECK , L UCA T REVISAN , AND M ADHUR T ULSIANI: A linear round lower bound
for Lovász-Schrijver SDP relaxations of vertex cover. In Proc. 22nd IEEE Conf. on Computational
Complexity (CCC’07), pp. 205–216. IEEE Comp. Soc. Press, 2007. [doi:10.1109/CCC.2007.2] 271,
281, 284
[28] G RANT S CHOENEBECK , L UCA T REVISAN , AND M ADHUR T ULSIANI: Tight integrality gaps for
Lovász-Schrijver LP relaxations of vertex cover and max cut. In Proc. 39th STOC, pp. 302–310.
ACM Press, 2007. [doi:10.1145/1250790.1250836] 271
[29] H ANIF D. S HERALI AND WARREN P. A DAMS: A hierarchy of relaxations between the continuous
and convex hull representations for zero-one programming problems. SIAM J. Discrete Math.,
3(3):411–430, August 1990. [doi:10.1137/0403036] 271, 274
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 287
S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T ULSIANI
[30] I ANNIS T OURLAKIS: Towards optimal integrality gaps for hypergraph vertex cover in the Lovász-
Schrijver hierarchy. In Proc. 8th Internat. Workshop on Approximation Algorithms for Com-
binatorial Optimization Problems (APPROX’05), volume 3624, pp. 233–244. Springer, 2005.
[doi:10.1007/11538462_20] 271
[31] I ANNIS T OURLAKIS: New lower bounds for vertex cover in the Lovász-Schrijver hierarchy. In
Proc. 21st IEEE Conf. on Computational Complexity (CCC’06), pp. 170–182. IEEE Comp. Soc.
Press, 2006. [doi:10.1109/CCC.2006.28] 271
[32] M ADHUR T ULSIANI: CSP gaps and reductions in the Lasserre hierarchy. In Proc. 41st STOC, pp.
303–312. ACM Press, 2009. [doi:10.1145/1536414.1536457] 271
AUTHORS
Siavosh Benabbas [About the author]
PhD Candidate
University of Toronto, Toronto, Ontario, Canada
siavosh cs toronto edu
http://www.cs.toronto.edu/~siavosh
Konstantinos Georgiou [About the author]
Post-doctoral fellow
Department of Combinatorics and Optimization
Faculty of Mathematics
University of Waterloo, Waterloo, Ontario, Canada
k2georgiou math uwaterloo ca
http://www.math.uwaterloo.ca/~k2georgi/
Avner Magen [About the author]
Formerly Associate Professor
University of Toronto, Toronto, Ontario, Canada
http://www.cs.toronto.edu/~avner
Madhur Tulsiani [About the author]
Assistant Professor
Toyota Technological Institute at Chicago, Chicago, IL, USA
madhurt ttic edu
http://ttic.uchicago.edu/~madhurt/
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 288
SDP G APS FROM PAIRWISE I NDEPENDENCE
ABOUT THE AUTHORS
S IAVOSH B ENABBAS got his B. S. from Sharif University of Technology under the su-
pervision of Mohammad Ghodsi in the Department of Computer Engineering. Since
2006, Siavosh has been a graduate student in the Department of Computer Science at
the University of Toronto. There, he received his M. S. under the supervision of Avner
Magen and Charles Rackoff, while he is currently anticipating his graduation with a
Ph. D. supervised by Toni Pitassi. Siavosh is interested in questions touching on Linear
Programming and Semidefinite Programming Relaxations, their Integrality Gaps and
their applications to Combinatorial Optimization.
KONSTANTINOS G EORGIOU (or Costis as friends call him) did his undergraduate studies at
the Department of Mathematics at the University of Athens (1998-2002), from where
he also received his M. S. in Logic and Algorithms (2002-2004). In 2005 he moved to
Toronto where he received his Ph. D. under the supervision of Avner Magen and Toni
Pitassi (2010). Currently, he is a postdoctoral fellow at the Department of Combinatorics
and Optimization at the University of Waterloo, working on projects varying from Convex
Optimization to Complexity Theory to Combinatorial Optimization to Algorithmic Game
Theory. Costis spends his free time in his kitchen where he experiments with flavors and
recipes.
AVNER M AGEN (1968-2010) did his undergraduate and graduate studies at Hebrew Uni-
versity and received his Ph. D. in Computer Science in 2002 under the supervision of
Nati Linial. After holding a postdoctoral fellowship at NEC Research in Princeton, NJ,
he joined the University of Toronto in 2002, first as a postdoctoral fellow, and then
as an Assistant Professor in 2004. He was promoted to Associate Professor in 2009.
Avner was a superb scholar, making fundamental contributions to a number of areas of
theoretical computer science that include Metric Embeddings, Sublinear Algorithms,
Convex Programming, Computational Geometry, and Approximation Algorithms. He
was a wonderful colleague with a terrific sense of humor and great energy. He was a
dedicated research supervisor and a superb teacher. He died at 42 in an avalanche while
on a climbing tour in Alaska. He is sorely missed by his family, friends, colleagues, and
students.
M ADHUR T ULSIANI did his B. Tech. in Computer Science at IIT Kanpur, mentored by
Professor Somenath Biswas (2001-05). He completed his Ph. D. at UC Berkeley (2005-
09) under Luca Trevisan. After graduation he spent two years as a postdoc at the Institute
for Advanced Study and Princeton University, and is currently an assistant professor at
the Toyota Technological Institute at Chicago. His research interests include Complexity
Theory, Optimization, Approximation and Inapproximability, Pseudorandomness, and
Cryptography.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 269–289 289