Authors Venkatesan Guruswami, Euiwoong Lee,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2015
Towards a Characterization of
Approximation Resistance
for Symmetric CSPs
Venkatesan Guruswami∗ Euiwoong Lee†
Received December 26, 2015; Revised August 7, 2016; Published June 13, 2017
Abstract: A Boolean constraint satisfaction problem (CSP) is called approximation re-
sistant if independently setting variables to 1 with some probability α achieves the best
possible approximation ratio for the fraction of constraints satisfied. We study approximation
resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction
Problems (SCSPs), where satisfaction of each constraint only depends on the number of true
literals in its scope. Thus a SCSP of arity k can be described by a subset S ⊆ {0, 1, . . . , k} of
allowed number of true literals.
For SCSPs without negation, we conjecture that a simple sufficient condition to be
approximation resistant by Austrin and Håstad is indeed necessary. We show that this
condition has a compact analytic representation in the case of symmetric CSPs (depending
A conference version of this paper appeared in the Proceedings of the 18th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX), 2015 [10].
∗ Supported in part by CCF-1115525.
† Supported in part by CCF-1115525 and Samsung Scholarship.
ACM Classification: F.2.2
AMS Classification: 68W25
Key words and phrases: inapproximability, UG-hardness, constraint satisfaction, semidefinite program-
ming
© 2016 Venkatesan Guruswami and Euiwoong Lee
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a003
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
only on the gap between the largest and smallest numbers in S), and provide the rationale
behind our conjecture. We prove two interesting special cases of the conjecture, (i) when
S is an interval (i. e., S = {i | ` ≤ i ≤ r} for some ` ≤ r) and (ii) when S is even (i. e.,
s ∈ S ⇔ k − s ∈ S). For SCSPs with negation, we prove that the analogous sufficient
condition by Austrin and Mossel is necessary for the same two cases, though we do not pose
an analogous conjecture in general.
1 Introduction
Constraint Satisfaction Problems (CSPs) are among the most fundamental and well-studied classes of
optimization problems. Given a fixed integer k and a predicate Q ⊆ {0, 1}k , an instance of CSP(Q)
without negation is specified by a set of variables, X = {x1 , . . . , xn }, on the domain {0, 1}, and a set
of constraints, C = {C1 , . . . ,Cm }, where each constraint C j = (x j1 , . . . , x jk ) is a k-tuple of variables.
An assignment σ : X → {0, 1} satisfies C j if (σ (x j1 ), . . . , σ (x jk )) ∈ Q. For an instance of CSP(Q)
with negation, each constraint C j is additionally given offsets (b j1 , . . . , b jk ) ∈ {0, 1}k and is satisfied if
(σ (x j1 ) ⊕ b j1 , . . . , σ (x jk ) ⊕ b jk ) ∈ Q where ⊕ denotes the addition in F2 . The goal is to find an assignment
that satisfies as many constraints as possible.
CSPs include a large number of famous problems such as Max-SAT (with negation), and Max-Cut
and Max-Set-Splitting (without negation). They have always played a crucial role in computational
complexity theory, as many breakthroughs, such as the NP-completeness of 3-SAT, the Probabilistically
Checkable Proofs (PCP) theorem, and the Unique Games Conjecture (UGC) study hardness of certain
CSPs. Based on these advances, recent work on approximability of CSPs has focused on characterizing
every CSP according to its approximation resistance. We define random assignments to be the class of
algorithms that assign xi ← 1 with some probability α independently. A CSP is called approximation
resistant, if for any ε > 0, it is NP-hard to have a (ρ ∗ + ε)-approximation algorithm, where ρ ∗ is the
approximation ratio achieved by the best random assignment. Even assuming the UGC, a complete
characterization of approximation resistance has not been found. In previous work, authors have either
changed the notion of approximation resistance or studied a subclass of CSPs to find a characterization.
More general results tend to suggest more complex characterizations.
In the present paper we consider a natural subclass of CSPs where a predicate Q is symmetric, i. e.,
for any permutation π : [k] → [k], (x1 , . . . , xk ) ∈ Q if and only if (xπ(1) , . . . , xπ(k) ) ∈ Q. Equivalently, for
every such Q, there exists S ⊆ [k] ∪ {0} such that (x1 , . . . , xk ) ∈ Q if and only if (x1 + · · · + xk ) ∈ S. Let
SCSP(S) denote such a symmetric CSP. While symmetry is a significant restriction, it is a natural one
that still captures a number of fundamental problems, including Max-SAT, Max-Not-All-Equal-SAT,
t-out-of-k-SAT (with negation), and Max-Cut, Max-Set-Splitting (without negation). See Appendix A for
their definitions.
Many papers in this line of work have focused on CSPs with negation; Austrin and Håstad [2] is
a notable exception. We feel that the aforementioned problems without negation have a very natural
interpretation as (hyper)graph coloring and are worth studying.
There is a simple sufficient condition to be approximation resistant due to Austrin and Mossel [4]
with negation, and due to Austrin and Håstad [2] without negation. For SCSPs, we show that these simple
sufficient conditions can be further simplified and understood more intuitively, and suggest that they
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 2
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
might also be necessary for and thus precisely characterize approximation resistance. We prove it for two
natural special cases (which capture all problems mentioned in the last paragraph) for SCSPs with as
well as without negation and provide reasons that we believe this is true at least for all SCSPs without
negation.
1.1 Related work
Given the importance of CSPs and the variety of problems that can be formulated as a CSP, it is a
natural task to classify all CSPs according to their computational complexity. For the task of deciding
satisfiability (i. e., deciding whether there is an assignment that satisfies every constraint), the work of
Schaefer [15] in 1978 proved that every CSP over the Boolean domain is either in P or NP-hard, and
gave a complete characterization of these two cases.
However, such a classification seems much harder when we study approximability of CSPs. Since
the seminal work of Håstad [12], many natural problems have been proven to be approximation resis-
tant. Examples include Max-3-SAT and Max-3-LIN (with negation) and Max-4-Set-Splitting (without
negation). For Boolean CSPs of arity 3, putting together the hardness results of [12] with the algorithmic
results of Zwick [17], it is known that a CSP is approximation resistant if and only if it is implied by
parity. Characterizing approximation resistance of every CSP for larger arity k is a harder task. The Ph. D.
thesis of Hast [11] is devoted to this task for k = 4, and succeeds in classifying 354 out of 400 predicates.
The advent of the Unique Games Conjecture (UGC) [13], though it is not as widely believed as
P 6= NP, revived the hope to classify every CSP according to its approximation resistance. For CSPs
with negation, Austrin and Mossel [4] gave a simple sufficient condition to be approximation resistant,
namely the existence of a balanced pairwise independent distribution that is supported on the satisfying
assignments of the predicate. Austrin and Håstad [2] proved a similar sufficient condition for CSPs
without negation. They also proved that if this condition is not met, this predicate (both with and without
negation) is useful for some polynomial optimization—for every such Q, there is a k-variate polynomial
p(y1 , . . . , yk ) such that if we are given an instance of CSP(Q) that admits an (1 − ε)-satisfying assignment,
the altered problem, where we change the payoff of each constraint C j from
I[(x j1 ⊕ b j1 , . . . , x jk ⊕ b jk ) ∈ Q]
(where I[·] is the indicator function) to p(x j1 ⊕ b j1 , . . . , x jk ⊕ b jk ), admits an approximation algorithm that
does better than any random assignment.
Predicates that do not admit a pairwise independent distribution supported on their satisfying as-
signments can be expressed as the sign of a quadratic polynomial (see [2]). This motivates the study
of the approximability of such predicates, though it is known that there are approximation resistant
predicates that can be expressed as a quadratic threshold function and thus the sufficient condition of
Austrin and Mossel [4] is not necessary for approximation resistance. Still this motivates the question of
understanding which quadratic threshold functions can be approximated non-trivially.
Cheraghchi, Håstad, Isaksson, and Svensson [8] studied the simpler case of predicates which are the
sign of a linear function with no constant term, obtaining algorithms beating the random assignment
threshold of 1/2 in some special cases. Austrin, Benabbas, and Magen [1] conjectured that every such
predicate can be approximated better than a factor 1/2 and is therefore not approximation resistant. They
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 3
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
proved that the predicates that are the sign of symmetric quadratic polynomials with no constant term are
not approximation resistant.
Assuming the UGC, Austrin and Khot [3] gave a characterization of approximation resistance for
even k-partite CSPs,1 and Khot, Tulsiani, and Worah [14] gave a characterization of strong approximation
resistance for general CSPs. Strong approximation resistance roughly means hardness of finding an
assignment that deviates from the performance of the random assignment in either direction (i. e., it is
hard to also find an assignment satisfying a noticeably smaller fraction of constraints than the random
assignment). These two results are notable for studying approximation resistance of general CSPs, but
their characterizations become more complicated, which they suggest is necessary.
Without the UGC, even the existence of a pairwise independent distribution supported on the predicate
is not known to be sufficient for approximation resistance. Another line of work shows partial results either
by using a stronger condition [7], or by using a restricted model of computation (e. g., Sherali-Adams or
Lasserre hierarchy of convex relaxations) [16, 6, 5].
1.2 Our results
The present paper is initially motivated by a simple observation that for symmetric CSPs, the sufficient
condition to be approximation resistant by Austrin and Håstad [2] admits a more compact and intuitive
two-dimensional description in R2 .
Fix a positive integer k and denote [k] = {1, 2, . . . , k}. For s ∈ [k] ∪ {0}, let P(s) ∈ R2 be the point
defined by
s s(s − 1)
P(s) := , .
k k(k − 1)
For any s, P(s) lies on the curve
k 2 x
y= x − ,
k−1 k−1
which is slightly below the curve y = x2 for x ∈ [0, 1]. Given a subset S ⊆ [k] ∪ {0}, let PS := {P(s) : s ∈ S}
and conv(PS ) be the convex hull of PS . For symmetric CSPs, the condition of Austrin and Håstad depends
on whether this convex hull intersects a certain curve or a point.
For SCSP(S) without negation, the condition becomes whether conv(PS ) intersects the curve y = x2 .
If we let smin and smax be the minimum and maximum number in S respectively, by convexity of
k 2 x
y= x − ,
k−1 k−1
it is equivalent to that the line passing through P(smin ) and P(smax ) and y = x2 intersect, which is again
equivalent to (see Lemma 4.4)
(smax + smin − 1)2 4smax smin
≥ . (1.1)
k−1 k
1 CSP(Q) is called k-partite when the set of variables is partitioned into k subsets and each constraint has exactly one variable
from each subset. It is called even when (x1 , . . . , xk ) ∈ Q if and only if (x1 ⊕ 1, . . . , xk ⊕ 1) ∈ Q.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 4
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
1.0
0.8
0.6
0.4
0.2
0.0
0.0 0.2 0.4 0.6 0.8 1.0
Figure 1: An example when k = 10 and S = {2, 5, 8}. The solid curve is y = x2 and the dashed curve is
y = kx2 /(k − 1) − x/(k − 1), where all P(s) lie. In this case the triangle conv(PS ) intersects y = x2 , so
SCSP(S) is approximation resistant.
A simple calculation shows that the above condition is implied by
p
(smax − smin ) ≥ 2(smax + smin )
√
which in turn holds if (smax − smin ) ≥ 2 k. This means that SCP(S) is approximation resistant unless smin
and smax are very close. See Figure 1 for an example.
For general CSP(Q) with Q ⊆ {0, 1}k , Q is positively correlated if there are a distribution µ supported
on Q and p, ρ ∈ [0, 1] with ρ ≥ p2 such that
Pr[xi = 1] = p for every i ∈ [k], and
µ
Pr[xi = x j = 1] = ρ for every 1 ≤ i < j ≤ k.
µ
Austrin and Håstad [2] proved that CSP(Q) is approximate resistant if Q is positively correlated. For
SCSP(S), Lemma 4.3 shows that (1.1) holds if and only if QS is positively correlated where
QS := {(x1 , . . . , xk ) ∈ {0, 1}k : x1 + · · · + xk ∈ S} .
We conjecture that this simple condition completely characterizes approximation resistance of
symmetric CSPs without negation. Note that we exclude the cases where S contains 0 or k, since without
negation, a trivial deterministic strategy to give the same value to every variable satisfies every constraint.
Conjecture 1.1. For S ⊆ [k − 1], SCSP(S) without negation is approximation resistant if and only if (1.1)
holds.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 5
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
The hardness claim, the “if” part, is currently proved only under the UGC, but our focus is on the
algorithmic claim that the violation of (1.1) leads to an approximation algorithm that outperforms the
best random assignment. Even though we were not able to prove Conjecture 1.1, we explain the rationale
behind the conjecture and we prove it for the following two natural special cases in Section 2:
1. S is an interval: S contains every integer from smin to smax .
2. S is even: s ∈ S if and only if k − s ∈ S.
Theorem 1.2. If S ⊆ [k −1] and S is either an interval or even, SCSP(S) without negation is approximation
resistant if and only if (1.1) holds. (The hardness claim, i. e., the “if” part, is under the Unique Games
conjecture.)
For SCSP(S) with negation, the analogous condition is whether conv(PS ) contains a single point
(1/2, 1/4). This is equivalent to that
QS := {(x1 , . . . , xk ) ∈ {0, 1}k : x1 + · · · + xk ∈ S}
is balanced pairwise independent (see Section 4). While it is tempting to pose a conjecture similar
to Conjecture 1.1, we refrain from doing so due to the lack of evidence compared to the case without
negation. However, we prove the following theorem which shows that the analogous characterization
results at least for the two special cases introduced above.
Theorem 1.3. If S ⊂ [k] ∪ {0} and S is either an interval or even, SCSP(S) with negation is approximation
resistant if and only if conv(PS ) contains (1/2, 1/4). (The hardness claim, i. e., the “if” part, is under the
Unique Games conjecture.)
1.3 Techniques
We mainly focus on SCSPs without negation, and briefly sketch why the violation of (1.1) might lead
to an approximation algorithm that outperforms the best random assignment. Let α ∗ be the probability
that the best random assignment uses, and ρ ∗ be the expected fraction of constraints satisfied by it. Our
algorithms follow the following general framework: sample correlated random variables X1 , . . . , Xn , where
each Xi lies in [−α ∗ , 1 − α ∗ ], and independently round xi ← 1 with probability α ∗ + Xi .
Fix one constraint C = (x1 , . . . , xk ). (For SCSPs with negation, additionally assume that the offsets
are all 0.) Using symmetry, the probability that C is satisfied by the above strategy can be expressed as
" #!
k
ρ∗ + ∑ c` · EI∈([k]) ∏ Xi
`
`=1 i∈I
for some coefficients {c` }`∈[k] . These coefficients c` can be expressed in the following two ways.
• Let f (α) : [0, 1] → [0, 1] the be probability that a constraint is satisfied by a random assignment
with probability α. Then c` is proportional to f (`) (α ∗ ), the `-th derivative of f evaluated at α ∗ .
• Let Q = {(x1 , . . . , xk ) ∈ {0, 1}k : (x1 + · · · + xk ) ∈ S} be the predicate associated with S. When
α ∗ = 1/2, c` is proportional to the Fourier coefficient Q̂(T ) with |T | = `.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 6
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
Given this observation, α ∗ for SCSPs without negation has nice properties since it should be a global
maximum in the interval [0, 1]. In particular, it should be a local maximum so that c1 = f 0 (α) = 0 and
c2 , f 00 (α) ≤ 0. By modifying an algorithm by Austrin and Håstad [2], we prove that we can sample
X1 , . . . , Xn such that the average second moment E[Xi X j ] is strictly negative if (1.1) does not hold. By
scaling the Xi so that the product of at least three of the Xi becomes negligible, this idea results in
an approximation algorithm that outperforms the best random assignment, except in the degenerate
case where c2 = f 00 (α ∗ ) = 0 even though α ∗ is a local maximum. This is the main rationale behind
Conjecture 1.1 and we elaborate this belief more in Section 2. It is notable that our conjectured
characterization for the case without negation only depends on the minimum and the maximum number
in S, while α ∗ also depends on other elements.
For SCSPs with negation where α ∗ is fixed to be 1/2, the situation becomes more complicated since
c1 and f 0 (α) are not necessarily zero and there are many ways that conv(PS ) does not contain (1/2, 1/4).
(In the case of SCSPs without negation, the slope of the line separating conv(PS ) and y = x2 is always
positive, but this is not the case here.) Therefore, a complete characterization requires understanding
interactions among c1 , c2 , and the separating line. We found that the somewhat involved method of
Austrin, Benabbas, and Magen [1] gives a way to sample these X1 , . . . , Xn with desired first and second
moments to prove our results when S exhibits additional special structures, but believe that a new set of
ideas are required to give a complete characterization.
1.4 Organization
In Section 2, we study SCSPs without negation. We further elaborate our characterization in Section 2.1,
and provide an algorithm in Section 2.2. We study SCSPs with negation in Section 3.
2 Symmetric CSPs without negation
2.1 A 2-dimensional characterization
Fix k and S ⊆ [k − 1]. Our conjectured condition to be approximation resistant is that conv(PS ) intersects
the curve y = x2 , which is equivalent to (1.1). Austrin and Håstad [2] proved that this simple condition is
sufficient to be approximation resistant.
Theorem 2.1 (Austrin–Håstad). Let S ⊆ [k − 1] be such that (1.1) holds. Then, assuming the Unique
Games Conjecture, SCSP(S) without negation is approximation resistant.
They studied general CSPs and their condition is more complicated than stated here. See Section 4 to
see how it is simplified for SCSPs. We conjecture that for SCSPs, this condition is indeed equivalent to
approximation resistance.
Conjecture 2.2 (Restatement of Conjecture 1.1). For S ⊆ [k − 1], SCSP(S) without negation is approxi-
mation resistant if and only if (1.1) holds.
To provide our rationale behind the conjecture, we define the function f : [0, 1] → [0, 1] to be the
probability that one constraint is satisfied by the random assignment that gives xi ← 1 independently with
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 7
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
0.35
0.25
0.12 0.30
0.10 0.20 0.25
0.08 0.20
0.15
0.06 0.15
0.10
0.04 0.10
0.05
0.02 0.05
0.00 0.00 0.00
0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
Figure 2: Examples for k = 36. Left: S = {18}, (1.1) is not satisfied, unimodal with α ∗ = 1/2,
f 00 (1/2) < 0. Middle: S = {15, 21}, (1.1) is satisfied with equality, unimodal with α ∗ = 1/2, but
f 00 (1/2) = 0. Right: S = {14, 22}, (1.1) is satisfied with slack, bimodal with two α ∗ , but f 00 (α ∗ ) < 0.
probability α:
k s
f (α) = ∑ α (1 − α)k−s .
s∈S s
Let α ∗ ∈ [0, 1] be a value that maximizes f (α), and ρ ∗ := f (α ∗ ). The value α ∗ may not be unique.
In Section 2.2, we prove that S is not approximation resistant if there exists such an α ∗ with a negative
second derivative.
Theorem 2.3. S ⊆ [k −1] be such that (1.1) does not hold and there exists α ∗ ∈ [0, 1] such that f (α ∗ ) = ρ ∗
and f 00 (α ∗ ) < 0. Then, there is a randomized polynomial-time algorithm for SCSP(S) that satisfies strictly
more than ρ ∗ fraction of constraints in expectation.
Since f (0) = f (1) = 0 < ρ ∗ , every α ∈ [0, 1] with f (α) = ρ ∗ must be a local maximum, so it should
have f 0 (α) = 0 and f 00 (α) ≤ 0. If α is a local maximum, f 00 (α) = 0 also implies f 000 (α) = 0, so ruling
out this degeneracy at a global maximum gives the complete characterization!
Ruling out this degeneracy at a global maximum does not seem to be closely related to the general
shape of f (α) or S. It might still hold even if f (α) has multiple global maxima, or S satisfies (1.1) so
that SCSP(S) is approximation resistant.
However, the examples in Figure 2 led us to believe that the condition (1.1) is also related to
general shape of f . When S contains two numbers ` and r with ` + r = k, as the two numbers move
far apart, f turns from unimodal to bimodal, and the transition happens exactly when (1.1) begins to
hold. Furthermore, the degenerate case f 0 (α ∗ ) = f 00 (α ∗ ) = 0 happens when (1.1) holds with equality.
Intuitively, when the two numbers ` and r are far apart, the best strategy is to focus on only one of them
(i. e., α ∗ ≈ `/k or r/k) so f is bimodal. If ` and r are close enough, it is better to target in the middle to
satisfy both ` and r, so f becomes unimodal with a large negative curvature at α ∗ .
Having more points between ` and r seems to strengthen the above intuition, and removing the
assumption that ` + r = k only seems to add algebraic complication without hurting the intuition. Thus,
we propose the following stronger conjecture that implies Conjecture 1.1.
Conjecture 2.4. If (1.1) does not hold, then f (α) is unimodal in [0, 1] with the unique maximum at α ∗ ,
and f 00 (α ∗ ) < 0.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 8
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
While we are unable to prove Conjecture 2.4 for every S, we establish it for the case when S is either
an interval (Section 2.3) or even (Section 2.4), thus proving Theorem 1.2.
2.2 Algorithm
Let α ∗ ∈ [0, 1] be such that f (α ∗ ) = ρ ∗ and f 00 (α ∗ ) < 0. Furthermore, suppose that S does not satisfy (1.1).
We give a randomized approximation algorithm which is guaranteed to satisfy strictly more than ρ ∗
fraction of constraints in expectation, proving Theorem 2.3. Let D := D(k) be a large constant to be
determined later. Our strategy is the following.
1. Sample (X1 , . . . , Xn ) from some correlated multivariate normal distribution where each Xi has mean
0 and variance at most σ 2 for some σ := σ (k).
2. For each i ∈ [n], set
∗ if Xi < −Dα ∗ ,
−Dα
Xi0 = D(1 − α ∗ ) if Xi > D(1 − α ∗ ) ,
Xi otherwise,
Xi0
so that α ∗ + is always in [0, 1].
D
Xi0
3. Set xi ← 1 independently with probability α ∗ + .
D
Fix one constraint C and suppose that C = (x1 , . . . , xk ). We consider a multivariate polynomial
yi yi
g(y1 , . . . , yk ) := ∑ ∏ α ∗ + ∏ 1 − α ∗
− .
T ⊆[k], i∈T
D i∈[k]\T D
|T |∈S
Note that g(X10 , . . . , Xk0 ) is equal to the probability that the constraint C is satisfied. By symmetry, for
any 1 ≤ i1 < · · · < i` ≤ k, the coefficient of a monomial yi1 yi2 . . . yi` only depends on `. Let c` be this
coefficient.
(k − l)! (`) ∗
Lemma 2.5. c` = f (α ).
k!D`
Proof. Note that g(y, y, . . . , y) = f (α ∗ + y/D), which has the Taylor expansion
k
f (`) (α ∗ ) y `
∑ .
`=0 `! D
Since g is multilinear, by symmetry, the coefficient of a monomial yi1 yi2 . . . yi` in g(y1 , . . . , yk ) is equal to
the coefficient of y` in f (α ∗ + y/D) divided by k` , which is
(k − `)! (`) ∗
c` = f (α ) .
k!D`
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 9
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
We analyze the overall performance of this algorithm. Let D` be the distribution on [n]
` where we
sample a constraint C uniformly at random, sample ` distinct variables from C` , and output their indices.
We prove the following lemma, which implies that by taking large D, the effect of truncation from Xi to
Xi0 and the contribution of monomials of degree greater than two become small.
Lemma 2.6. The expected fraction of constraints satisfied by the above algorithm is at least
f 00 (α ∗ )
∗ k 1 ∗ 1
ρ + c2 E(i, j)∼D2 [Xi X j ] − Ok 3
=ρ + 2
E(i, j)∼D2 [Xi X j ] − Ok ,
2 D 2D D3
where Ok (·) is hiding constants depending on k.
Proof. For any s ∈ {1, . . . , k − 1}, the function fs (α) = ks α s (1 − α)k−s is unimodal in [0, 1] with the
maximum at α = s/k. As long as S does not contain 0 or k,
f (α) = ∑ fs (α)
s∈S
cannot have a local maximum in [0, 1/k) and (1 − 1/k, 1], so we can assume that α ∗ ∈ [1/k, 1 − 1/k]. For
any 1 ≤ ` ≤ k and 1 ≤ i1 < · · · < i` ≤ k, we apply Lemma 5.1 (set D ← D/k),
" # " #
` `
E ∏ Xi j − E ∏ Xi0 j
≤ 2` · σ ` · `! · e−D/k` .
j=1 j=1
If we expand f (α) = ∑k`=0 a` α ` , each coefficient a` has magnitude at most 2k , which means that
| f (α ∗ )| is bounded by k2k k!. Therefore, any |c` | is at most k2k k!. Let cmax be this quantity. Summing
(`)
over this error for all monomials, the probability that a fixed constraint C = {x1 , . . . , xk } is satisfied is
2
E[g(X10 , . . . , Xk0 )] ≥ E[g(X1 , . . . , Xk )] − cmax · 22k · σ k · k! · e−D/k
k
2
= ρ ∗ + ∑ c` ∑ Xi1 Xi2 . . . Xi` − Ok e−D/k
`=1 1≤i1 <···<i` ≤k
k
2
= ρ ∗ + ∑ c` ∑ Xi1 Xi2 . . . Xi` − Ok e−D/k .
`=1 1≤i1 <···<i` ≤k
Averaging over m constraints, the expected fraction of satisfied constraints is at least
k
∗ k 2
ρ + ∑ c` E(i1 ,...,i` )∼D` [Xi1 . . . Xi` ] − Ok e−D/k
`=1 `
k
∗ k k 2
= ρ + c2 E(i1 ,i2 )∼D2 [Xi1 Xi2 ] + ∑ c` E(i1 ,...,i` )∼D` [Xi1 . . . Xi` ] − Ok e−D/k
2 `=3 `
k 1
= ρ ∗ + c2 E(i1 ,i2 )∼D2 [Xi1 Xi2 ] − Ok
2 D3
f 00 (α ∗ )
1
= ρ∗ + E [X X
i j ] − O k ,
2D2 (i, j)∼D2 D3
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 10
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
where the first equality follows from the fact that E[Xi ] = 0 for all i. Recall that
(k − `)! (`) ∗
c` = f (α )
k!D`
so that |c` | = Ok (1/D` ).
Therefore, if we have a way to sample X1 , . . . , Xn such that each Xi has mean 0 and variance at most
σ 2 , and
E(i, j)∼D2 [Xi X j ] < −δ
for some δ := δ (k) > 0, taking D large enough ensures that the algorithm satisfies strictly more than ρ ∗
fraction of constraints. We now show how to do such a sampling. Our basic intuition is that if S does not
satisfy (1.1), there is no positively correlated distribution supported by
QS := {(x1 , . . . , xk ) : x1 + · · · + xk ∈ S} ,
which helps to find a distribution with negative correlation.
We assume that for some ε := ε(k) > 0, the given instance admits a solution that satisfies (1 − ε) frac-
tion of constraints. Otherwise, the random assignment with probability α ∗ guarantees the approximation
ratio of ρ ∗ /(1 − ε). The following lemma completes the proof of Theorem 2.3.
Lemma 2.7. Suppose that S does not satisfy (1.1). For sufficiently small ε, δ > 0 and sufficiently large
σ all depending only on k, given an instance of SCSP(S) where (1 − ε) fraction of constraints are
simultaneously satisfiable, it is possible to sample (X1 , . . . , Xn ) from a multivariate normal distribution
such that each Xi has mean 0 and variance bounded by σ 2 , and
E(i, j)∼D2 [Xi X j ] < −δ .
Proof. Recall that (1.1) is equivalent to the fact that the line ` passing through P(smin ) and P(smax )
intersects the curve y = x2 . Let a be the value such that the vector (a, −1) is orthogonal to `. The value a
is strictly positive since ` has a positive slope. If ` and y = x2 do not intersect, there is a line with the
same slope as ` that strictly separates y = x2 and {P(s) : s ∈ S}, i. e., there exists c ∈ R such that
• ax − y + c > γ > 0 for (x, y) ∈ {P(s) : s ∈ S};
• ax − x2 + c < 0 for any x ∈ R ⇒ c < −a2 /4.
Consider a constraint C = (x1 , . . . , xk ). Since
Ei∈[k] [xi ], Ei6= j∈[k] [xi x j ] = P(x1 + · · · + xk ) ,
if C is satisfied,
aEi∈[k] [xi ] − Ei6= j∈[k] [xi x j ] + c > γ .
Let
η := − min aEi∈[k] [xi ] − Ei6= j∈[k] [xi x j ] + c .
x1 ,...,xk ∈{0,1}
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 11
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
We solve the following semidefinite program (SDP):
maximize aEi∈D1 [hv0 , vi i] − Ei, j∈D2 [hvi , v j i] + c
subject to ||v0 || = 1
hvi , v0 i = ||vi ||2 for all i ∈ [n]
Note that hvi , v0 i = ||vi ||2 implies ||vi || ≤ 1. For any assignment to x1 , . . . , xn , setting vi = xi v0 satisfies
that xi = hv0 , vi i and xi x j = hvi , v j i. Since at least (1 − ε) fraction of the constraints can be simultaneously
satisfied, the optimum of the above SDP is at least (1 − ε)γ − εη. Given γ > 0 and η, take sufficiently
small ε, δ > 0 such that (1 − ε)γ − εη = δ . There are finitely many S (thus γ and η) for each k, so ε and
δ can be taken to depend only on k. Given vectors v0 , v1 , . . . , vn , we sample X1 , . . . , Xn by the following
simple procedure:
1. Sample a vector g whose coordinates are independent standard normal.
2. Let Xi = hg, vi − (a/2)v0 i.
It is clear that E[Xi ] = 0 for each i, and
a
E[Xi2 ] = ||vi − v0 ||2 ≤ (a + 1)2 + 1 ,
2
so taking σ := σ (k) large enough ensures that the variance of each Xi is bounded by σ 2 . We now compute
the second moment.
hD a a Ei
Ei, j∼D2 [Xi X j ] = Ei, j∼D2 vi − v0 , v j − v0
2 2
a2
= Ei, j∼D2 [hvi , v j i] − aEi∈D1 [hvi , v0 i] +
4
< Ei, j∼D2 [hvi , v j i] − aEi∈D1 [hvi , v0 i] − c
≤ − ((1 − ε)γ − εη) = −δ ,
where the first inequality follows from c < −a2 /4 and the second follows from the optimality of our
SDP.
2.3 Case of interval S
We study properties of f (α) when S is an interval, i. e., S = {smin , smin + 1, . . . , smax − 1, smax }, and prove
Conjecture 2.4 for this case. One notable fact is that as long as S is an interval, the conclusion of
Conjecture 2.4 is true even if S does satisfy (1.1) and becomes approximation resistant.
Lemma 2.8. Suppose S ⊆ [k −1] is an interval. Then, f (α) is unimodal in [0, 1] with the unique maximum
at α ∗ and f 00 (α ∗ ) < 0.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 12
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
Proof. Let ` := smin and r = smax . Given
r
k s
f (α) = ∑ α (1 − α)k−s
s=` s
and
r
k
f 0 (α) = ∑ sα s−1 (1 − α)k−s − (k − s)α s (1 − α)k−s−1 ,
s=` s
since
k k
(k − s) = (s + 1) ,
s s+1
we have
k k
f 0 (α) = `α `−1 (1 − α)k−` − (k − r)α r (1 − α)k−r−1 .
` r
If 0 < α < 1, setting β := α/(1 − α) gives a unique non-zero solution to f 0 (β ) = 0. This proves the
unimodality. For the second derivative,
00 k `−2 k
f (α) = `(` − 1)α (1 − α) − k−`
`(k − `)α `−1 (1 − α)k−`−1 +
` `
k r k−r−2 k
(k − r)(k − r − 1)α (1 − α) − r(k − r)α r−1 (1 − α)k−r−1
r r
k
= `α `−2 (1 − α)k−`−1 ((` − 1)(1 − α) − (k − `)α) +
`
k
(k − r)α r−1 (1 − α)k−r−2 ((k − r − 1)α − r(1 − α)) .
r
Since
`−1 ` r r
< ≤ α∗ ≤ <
k−1 k k k−1
we conclude that
(` − 1)(1 − α ∗ ) − (k − `)α ∗ = (` − 1) − (k − 1)α ∗ < 0
and
(k − r − 1)α ∗ − r(1 − α ∗ ) = (k − 1)α ∗ − r < 0 ,
so that f 00 (α ∗ ) < 0.
2.4 Case of even S
We study properties of f (α) when S is even, i. e., s ∈ S if and only if k − s ∈ S, and prove Conjecture 2.4
for this case. We first simplify (1.1) for this setting. If we let ` := smin and r := smax = k − `, (1.1) is
equivalent to
(` + r − 1)2 4`r
≥ ⇔ k(k − 1) ≥ 4`r ⇔ (r − `)2 ≥ k .
k−1 k
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 13
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
Therefore, (1.1) is equivalent to √
r−` ≥ k. (2.1)
Lemma 2.9. Suppose S ⊆ [k − 1] is even. If (2.1) does not hold, f (α) is unimodal in [0, 1] with the
unique maximum at α ∗ = 1/2 and f 00 (α ∗ ) < 0.
Proof. Given a even S, let S1 = {s ∈ S : s ≤ k/2}. When we write fS to denote the dependence of f on S,
we can decompose
fS (α) = ∑ f{s,k−s} (α) ,
s∈S1
so the following claim proves the lemma.
√
Claim 2.10. Let ` ≤ k/2 and r = k − ` such that r − ` < k ⇔ k(k − 1) < 4`r. Let S = {`, r}. f is
unimodal with the unique maximum at 1/2, and f 00 (1/2) < 0.
Proof. Note that f is symmetric around α = 1/2. If there exists a local maximum at α 0 ∈ (0, 1/2), f also
has a local maximum at (1 − α 0 ) with the same value, so there must exist a local minimum in (α 0 , 1 − α 0 ).
In particular, there is α ∈ (α 0 , 1 − α 0 ) such that f 0 (α) = 0 and f 00 (α) ≥ 0. We prove that such an α
cannot exist.
0 k `−1 k r−1
f (α) = 0 ⇔ r−1
α (1 − α) (` − kα) + α (1 − α)`−1 (r − kα) = 0
` r
k k
`−1 r−1
r−`
` α (1 − α) ` (1 − α) (kα − r)
⇔ k
= k
=− .
(kα − `)
r−1 (1 − α) `−1 r−`
r α r α
Similarly,
k
r−`
00 ` (1 − α) r(r − 1)(1 − α)2 − 2r`α(1 − α) + `(` − 1)α 2
f (α) ≥ 0 ⇔ ≥ − .
k `(` − 1)(1 − α)2 − 2r`α(1 − α) + r(r − 1)α 2
r−`
r α
By symmetry, we can assume α ≥ 1/2, so that (kα − `) ≥ 0 and
`(` − 1)(1 − α)2 − 2r`α(1 − α) + r(r − 1)α 2 ≥ 0 .
Thus,
(kα − r) r(r − 1)(1 − α)2 − 2r`α(1 − α) + `(` − 1)α 2
≤
(kα − `) `(` − 1)(1 − α)2 − 2r`α(1 − α) + r(r − 1)α 2
⇔ (kα − r)(`(` − 1)(1 − α)2 − 2r`α(1 − α) + r(r − 1)α 2 )
≤ (kα − `)(r(r − 1)(1 − α)2 − 2r`α(1 − α) + `(` − 1)α 2 )
⇔ α 2 (`3 − r3 − (`2 − r2 ) + r`(` − r) − 2k(`2 − r2 ) + 2k(` − r)) +
α(k(`2 − r2 ) − k(` − r)) − r`(` − r) ≤ 0
⇔ α 2 (−k2 + k) + α(k2 − k) − r` ≥ 0 (divide by (` − r) and use ` + r = k).
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 14
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
However, α 2 (−k2 + k) + α(k2 − k) − r` has a negative leading coefficient and its discriminant is
(k2 − k)2 − 4r`(k2 − k) = (k2 − k)(k2 − k − 4r`) < 0
by the assumption of the claim.
Figure 2 shows examples where Lemma 2.9 is tight. When (2.1) holds with equality, f still has the
unique local maximum at 1/2 but f 00 (1/2) = 0, and even when (2.1) holds with small slack, two local
maxima start to appear. This phenomenon is one of the main reasons that we pose Conjecture 2.4. Though
we were not able to prove the conjecture for the general case, we believe that the violation of (1.1) not
only allows us to sample random variables with desired second moments but also ensures that f (α) is a
nice unimodal curve.
3 Approximability of symmetric CSPs with negation
Fix k and S ⊂ [k] ∪ {0}. In this section, we consider SCSP(S) with negation and prove Theorem 1.2. Note
that in this section we allow S to contain 0 or k. For example, famous Max-3-SAT is 3-SCSP({1, 2, 3}).
We still exclude the trivial case S = [k] ∪ {0}.
The condition we are interested in is whether conv(PS ) contains (1/2, 1/4). In SCSPs with negation,
the sufficient condition of Austrin and Mossel on general CSPs to be approximation resistant becomes
equivalent to it. See Section 4 to see the equivalence.
Theorem 3.1 (Austrin–Håstad [2]). Fix k and let S ⊂ [k] ∪ {0} be such that conv(PS ) contains (1/2, 1/4).
Then, assuming the Unique Games Conjecture, SCSP(S) with negation is approximation resistant.
On the other hand, we now show that the algorithm of Austrin et al. [1], which is inspired by Hast [11],
can be used to show that if S is an interval or even and conv(PS ) does not contain (1/2, 1/4), SCSP(S) is
not approximation resistant.
Let f : {0, 1}k → {0, 1} be the function such that f (x1 , . . . , xk ) = 1 if and only if (x1 + · · · + xk ) ∈ S.
Define the inner product of two functions as
h f , gi = Ex∈{0,1}k [ f (x)g(x)] ,
and for T ⊆ [k], let
χT (x1 , . . . , xk ) = ∏(−1)xi .
i∈T
It is well known that {χT }T ⊆[k] form an orthonormal basis and every function has a unique Fourier
expansion with respect to this basis,
f = ∑ fˆ(T )χT , fˆ(T ) := h f , χT i .
T ⊆[k]
Define
f =d (x) = ∑ fˆ(S)χT (x) .
|T |=d
The main theorem of Austrin et al. [1] is
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 15
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
Theorem 3.2 (Austrin–Benabbas–Magen). Suppose that there exists η ∈ R such that
2η 2
√ f =1 (x) + f =2 (x) > 0 (3.1)
2π π
for every x ∈ f −1 (1). Then there is a randomized polynomial-time algorithm that approximates SCSP(S)
better than the random assignment in expectation.
We compute f =1 and f =2 :
1 k−1 k−1
fˆ({1}) = h f , χ{1} i = k ∑ − ,
2 s∈S s s−1
1 k−2 k−2 k−2
fˆ({1, 2}) = h f , χ{1,2} i = k ∑ −2 + .
2 s∈S s s−1 s−2
By symmetry, fˆ(T ) =: fˆ1 is the same for all |T | = 1 and fˆ(T ) =: fˆ2 is the same for all |T | = 2. If we let
s = x1 + · · · + xk ,
s
f =1 (x) = fˆ1 ∑ (−1)xi = k fˆ1 Ei∈[k] [−2xi + 1] = k fˆ1 −2 + 1 ,
i∈[k]
k
=2 ˆ xi +x j k ˆ k ˆ s(s − 1) s
f (x) = f2 ∑ (−1) = f2 Ei6= j [(−2xi + 1)(−2x j + 1)] = f2 4 −4 +1 .
i6= j 2 2 k(k − 1) k
When S is an interval. Let S = {`, ` + 1, . . . , r − 1, r}. If r ≤ k/2, we have (−2s/k + 1) ≤ 0 for all
s ∈ S, so choosing η either large enough or small enough ensures (3.1). Similarly, if ` ≥ k/2, (3.1) holds.
Therefore, we assume that ` < k/2 and r > k/2, and compute fˆ2 .
r
ˆf2 = 1 ∑ k−2 k−2 k−2
−2 +
2k s=` s s−1 s−2
1 k−2 k−2 k−2 k−2
= k − + − .
2 `−2 `−1 r r−1
Since k−2 k−2 k−2 k−2
for k/2 < r < k, fˆ2 < 0 except when ` = 0 and
`−1 > `−2 for 0 < ` < k/2 and r−1 > r
r = k (i. e., S = [k] ∪ {0}).
If conv(PS ) does not contain (1/2, 1/4), there exist α, β ∈ R such that for any (a, b) ∈ conv(PS ),
1 1
α a− +β b− > 0.
2 4
If k is even, s := k/2 ∈ S and
1 s−1 s−1 1
P(s) = , where < ,
2 2(k − 1) 2(k − 1) 4
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 16
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
which implies β < 0 since the above inequality should hold for all s ∈ S. When k is odd (let k = 2s + 1),
s and s + 1 should be in S and
1 s2 s2
1 1
P(s) + P(s + 1) = , where < .
2 2 k(k − 1) k(k − 1) 4
Therefore, we can conclude β < 0 in any case. For any x ∈ f −1 (1) with s = x1 + · · · + xk and P(s) = (a, b),
2η 2
√ f =1 (x) + f =2 (x)
2π π
2η ˆ 2 k ˆ
= √ k f1 (−2a + 1) + f2 (4b − 4a + 1)
2π π 2
√2η k fˆ1 !
8 k ˆ 2π 1
= f2 8 k (−2a + 1) + β b − a +
βπ 2 ˆ 4
β π 2 f2
8 k ˆ α +β 1
= f2 − (−2a + 1) + β b − a +
βπ 2 2 4
√2η k fˆ1
α +β
and, by adjusting η so that 8 2πk = − ,
ˆ 2
β π 2 f2
8 k ˆ 1 1
= f2 α a − +β b−
βπ 2 2 4
> 0.
Therefore, (3.1) is satisfied if S is an interval and conv(S) does not contain (1/2, 1/4).
When S is even. Given S, let Q ∈ {0, 1}k be the predicate associated with S and f : {0, 1}k → {0, 1} be
the indicator function of Q. We want to show that when S is even,
2η 2
√ f =1 (x) + f =2 (x) > 0
2π π
is satisfied for any x ∈ f −1 (1). When S is even,
1 k − 1 k − 1 k − 1 k − 1
fˆ1 = k+1 ∑ − + − = 0.
2 s∈S s s−1 k−s k−s−1
We compute the sign of the contribution of each s to fˆ2 .
k−2 k−2 k−2
−2 + ≥ 0 ⇔ (k − s)(k − s − 1) − 2s(k − s) + s(s − 1) ≥ 0
s s−1 s−2
⇔ 4s2 − 4sk + k2 − k ≥ 0
√ √
k− k k+ k
⇔ s≤ or s ≥ .
2 2
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 17
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
We also consider the line passing P(s) and P(k − s). If we denote t = k − s, its slope is
t(t−1)−s(s−1)
k(k−1) t 2 − s2 − (t − s)
t−s = = 1,
k
(k − 1)(t − s)
and the value of this line at 1/2 is at least 1/4 when
s(s − 1) + (k − s)(k − s − 1) 1
≥ ⇔ 2s(s − 1) + 2(k − s)(k − s − 1) ≥ k(k − 1)
2k(k − 1) 4
√ √
k− k k+ k
⇔ s≤ or s ≥ .
2 2
Intuitively,
√ if we √consider the line of slope 1 that passes (1/2, 1/4), P(s) is below this √ line if
s ∈ ((k − k)/2, (k √ + k)/2). Let S 1 = S ∩ {0, 1, . . . , dk/2e}. If
√ 1 S contains a value s 1 ≤ (k − k)/2 and
a value s2 ≥ (k − k)/2 (including the case s1 = s2 = (k − k)/2 is an integer in S1 ), the line passing
P(s1 ) and P(k − s1 ) passes a point (1/2,t1 ) for some t1 ≥ 1/4 and the line passing P(s2 ) and P(k − s2 )
passes a point (1/2,t2 ) for some t2 ≤ 1/4. Therefore, conv(PS ) contains a point (1/2, 1/4) and S becomes
balanced pairwise independent. We consider the remaining two cases.
√
1. s < (k − k)/2 for all s ∈ S1 : fˆ2 > 0 and for all s ∈ S,
s 1 s(s − 1) 1
− − + − > 0.
k 2 k(k − 1) 4
Therefore, for any x ∈ f −1 with s = x1 + · · · + xk ,
2η 2 2 =2
√ f =1 (x) + f =2 (x) = f (x)
2π π π
2 k ˆ s(s − 1) s
= f2 4 −4 +1
π 2 k(k − 1) k
> 0.
√
2. s > (k − k)/2 for all s ∈ S1 : fˆ2 < 0 and for all s ∈ S,
s 1 s(s − 1) 1
− − + − < 0.
k 2 k(k − 1) 4
Similarly as above, for any x ∈ f −1 with s = x1 + · · · + xk , (3.1) is satisfied.
4 Austrin-Håstad condition for symmetric CSPs
This section explains how the condition of Austrin-Håstad [2] is simplified for SCSPs. They studied
general CSPs where a predicate Q is a subset of {0, 1}k . Note that given S ⊆ [k] ∪ {0}, SCSP(S) is
equivalent to CSP(Q) where
Q = {(x1 , . . . , xk ) ∈ {0, 1}k : (x1 + · · · + xk ) ∈ S} . (4.1)
Given Q, their general definition of pairwise independence and positive correlation is given below.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 18
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
Definition 4.1. Q is balanced pairwise independent if there is a distribution µ supported on Q such that
Prµ [xi = 1] = 1/2 for every i ∈ [k] and Prµ [xi = x j = 1] = 1/4 for every 1 ≤ i < j ≤ k.
Definition 4.2. Q is positively correlated if there are a distribution µ supported on Q and p, ρ ∈ [0, 1]
with ρ ≥ p2 such that Prµ [xi = 1] = p for every i ∈ [k] and Prµ [xi = x j = 1] = ρ for every 1 ≤ i < j ≤ k.
We prove that their definitions have simpler descriptions in R2 for symmetric CSPs. Recall that given
s ∈ [k] ∪ {0},
s s(s − 1)
P(s) = , ∈ R2 and PS := {P(s) : s ∈ S} .
k k(k − 1)
Lemma 4.3. Let S ⊆ [k] ∪ {0} and Q be obtained by (4.1). Q is pairwise independent if and only if
conv(PS ) contains (1/2, 1/4), and Q is positively correlated if and only if conv(PS ) intersects the curve
y = x2 .
Proof. We first prove the second claim of the lemma. Let Q be positively correlated with parameters p, ρ
(ρ ≥ p2 ) and the distribution µ such that Prµ [xi = 1] = p for all i, Prµ [xi = x j = 1] = ρ and for all i < j.
Let ν be the distribution of x1 + · · · + xk where (x1 , . . . , xk ) are sampled from µ.
hsi s(s − 1)
(p, ρ) = (Ei [xi ], Ei< j [xi x j ]) = Es∼ν , Es∼ν = Es∼ν [P(s)] ,
k k(k − 1)
proving that positive correlation of Q implies (p, ρ) ∈ conv(PS ). Since P(s) is strictly below the curve
y = x2 for any s ∈ [k − 1] and (p, ρ) is on or above this curve, conv(PS ) must intersect y = x2 .
Suppose that conv(PS ) intersects the curve y = x2 . There exists a distribution ν on S such that
Es∼ν [P(s)] = (p, p2 ). Let µs be the distribution on {0, 1}k that uniformly samples a string with exactly
s ones. Let µ be the distribution where s is sampled from ν and (x1 , . . . , xk ) is sampled from µs . By
definition, Prµ [xi = 1] and Prµ [xi = x j = 1] do not depend on choice of indices,
hsi
Pr[x1 = 1] = Eµ [x1 ] = Es∼ν Ex∼µs [x1 ] = Es∼ν = p , and
µ k
s(s − 1)
Pr[x1 = x2 = 1] = Eµ [x1 x2 ] = Es∼ν Ex∼µs [x1 x2 ] = Es∼ν = p2 ,
µ k(k − 1)
implying that (p, p2 ) ∈ conv(PS ).
The proof of the first claim is similar except that the curve y = x2 is replaced by (1/2, 1/4).
Lemma 4.4. conv(PS ) intersects the curve x = y2 if and only if
(smax + smin − 1)2 4smax smin
≥ .
k−1 k
Proof. Let ` = smin and r = smax . The line passing P(`) and P(r) has a slope
r(r−1)−`(`−1)
k(k−1) r+`−1
r−`
=
k
k−1
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 19
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
and a y-intercept b such that
`(` − 1) r + ` − 1 ` `(` − 1) − `(r + ` − 1) −`r
= · +b ⇔ b = = .
k(k − 1) k−1 k k(k − 1) k(k − 1)
This line intersects y = x2 if and only if
r+`−1 `r
x2 = x−
k−1 k(k − 1)
has a real root, which is equivalent to
r+`−1 2 (r + ` − 1)2 4`r
4`r
− ≥0⇔ ≥ .
k−1 k(k − 1) k−1 k
5 Technical proof
Lemma 5.1. Let (Y1 , . . . ,Y` ) be sampled from a multivariate normal distribution where each Yi has mean
0 and variance at most σ 2 . Let Y10 , . . . ,Y`0 be such that
Yi
if |Yi | ≤ D ,
0
Yi = D if Yi > D ,
−D if Yi < −D .
Then, for large enough D,
" # " #
` `
E ∏ Yi − E ∏ Yi0 ≤ 2` · σ ` · `! · e−D/` .
i=1 i=1
Proof. For each i ∈ [`], let Yi00 = Yi0 −Yi . Take D large enough so that
Z ∞ Z ∞
E[|Yi00 |` ] = 2 (y − D)` φ (y) ≤ 2 y` φ (y) ≤ e−D .
y=D y=D
Also each Yi , a normal random variable with mean 0 and variance σ , satisfies E[|Yi |` ] ≤ σ ` · `!. We have
" # " #
` `
E ∏ Yi − E ∏ Yi0
i=1 i=1
" #
= ∑ E ∏ Yi ∏ Yi00
T ⊆[`],T 6=[`] i∈T i∈T
/
1/` 1/`
≤ ∑ ∏ E[|Yi |` ] ∏ E[|Yi00 |` ] (by the generalized Hölder inequality [9])
T ⊆[`],T 6=[`] i∈T i∈T
/
≤ 2` · σ ` · `! · e−D/` .
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 20
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
A Some CSPs of interest
In the most general definition, a Boolean CSP is specified by not a single predicate Q but a family
Q = {Q1 , Q2 , . . . } of predicates where each Qi is a subset of {0, 1}ki for some ki . In CSP(Q), each
constraint is an application of a predicate from Q to a k-tuple of variables.
With negation. We list the CSPs with negation mentioned in the introduction.
• Max-SAT: Q = {Q1 , Q2 , . . . } where
Qi = {(x1 , . . . , xi ) ∈ {0, 1}i : x1 + · · · + xi ≥ 1} .
For Max-k-SAT, Q = {Qk }.
• Max-Not-All-Equal-SAT: Q = {Q2 , Q3 , . . . } where
Qi = {(x1 , . . . , xi ) ∈ {0, 1}i : 1 ≤ x1 + · · · + xi ≤ i − 1} .
For Max-Not-All-Equal-k-SAT, Q = {Qk }.
• t-out-of-k-SAT: Q = {Qk } where
Qk = {(x1 , . . . , xk ) ∈ {0, 1}k : x1 + · · · + xi = t} .
• Max-LIN: Q = ∪i∈N {Qi,0 , Qi,1 } where
Qi, j = {(x1 , . . . , xi ) ∈ {0, 1}i : x1 ⊕ · · · ⊕ xi = j} .
(Recall that ⊕ denotes the addition in F2 .) For Max-k-LIN, Q = {Qk,0 , Qk,1 }.
Without negation. We list the CSPs without negation mentioned in the introduction.
• Max-Set-Splitting: Q = {Q2 , Q3 , . . . } where
Qi = {(x1 , . . . , xi ) ∈ {0, 1}i : 1 ≤ x1 + · · · + xi ≤ i − 1}
(same as Max-Not-All-Equal-SAT). For Max-k-Set-Splitting, Q = {Qk }.
• Max-Cut is equivalent to Max-2-Set-Splitting.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 21
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
References
[1] P ER AUSTRIN , S IAVOSH B ENABBAS , AND AVNER M AGEN: On quadratic threshold CSPs. Discr.
Math. & Theoret. Comput. Sci., 14(2):205–228, 2012. Avilable at HAL. Preliminary version in
LATIN’10. 3, 7, 15
[2] P ER AUSTRIN AND J OHAN H ÅSTAD: On the usefulness of predicates. ACM Trans. Comput.
Theory, 5(1):1:1–1:24, 2013. Preliminary version in CCC’12. [doi:10.1145/2462896.2462897,
arXiv:1204.5662] 2, 3, 4, 5, 7, 15, 18
[3] P ER AUSTRIN AND S UBHASH K HOT: A characterization of approximation resistance for even
k-partite CSPs. In Proc. 4th Conf. on Innovations in Theoret. Comput. Sci. (ITCS’13), pp. 187–196.
ACM Press, 2013. [doi:10.1145/2422436.2422459, arXiv:1301.2731] 4
[4] 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, arXiv:0802.2300] 2, 3
[5] B OAZ BARAK , S IU O N C HAN , AND P RAVESH K. KOTHARI: Sum of squares lower
bounds from pairwise independence. In Proc. 47th STOC, pp. 97–106. ACM Press, 2015.
[doi:10.1145/2746539.2746625, arXiv:1501.00734] 4
[6] S IAVOSH B ENABBAS , KONSTANTINOS G EORGIOU , AVNER M AGEN , AND M ADHUR T UL -
SIANI : SDP gaps from pairwise independence. Theory of Computing, 8(12):269–289, 2012.
[doi:10.4086/toc.2012.v008a012] 4
[7] S IU O N C HAN: Approximation resistance from pairwise independent subgroups. J. ACM,
63(3):27:1–27:32, 2016. Preliminary versions in STOC’13 and ECCC. [doi:10.1145/2873054] 4
[8] M AHDI C HERAGHCHI , J OHAN H ÅSTAD , M ARCUS I SAKSSON , AND O LA S VENSSON: Approxi-
mating linear threshold predicates. ACM Trans. Comput. Theory, 4(1):2:1–2:31, 2012. Preliminary
version in APPROX’10. [doi:10.1145/2141938.2141940] 3
[9] W ING -S UM C HEUNG: Generalizations of Hölder’s inequality. Internat. J. Math.& Math. Sci.,
26(1):7–10, 2001. [doi:10.1155/S0161171201005658] 20
[10] V ENKATESAN G URUSWAMI AND E UIWOONG L EE: Towards a characterization of approximation
resistance for symmetric CSPs. In Proc. 18th Internat. Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX’15), pp. 305–322. Springer, 2015. Preliminary
version at ECCC. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.305] 1
[11] G USTAV H AST: Beating a Random Assignment: Approximating Constraint Satisfaction Problems.
Ph. D. thesis, KTH, Numerical Analysis and Computer Science, NADA, 2005. QC 20101020.
Avaliable at DiVA. 3, 15
[12] J OHAN H ÅSTAD: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Prelimi-
nary version in STOC’97. [doi:10.1145/502090.502098] 3
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 22
T OWARDS A C HARACTERIZATION OF A PPROXIMATION R ESISTANCE FOR S YMMETRIC CSP S
[13] S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767–775. ACM Press, 2002. Also in CCC’02. [doi:10.1145/509907.510017] 3
[14] S UBHASH K HOT, M ADHUR T ULSIANI , AND P RATIK W ORAH: A characterization of
strong approximation resistance. In Proc. 46th STOC, pp. 634–643. ACM Press, 2014.
[doi:10.1145/2591796.2591817, arXiv:1305.5500] 4
[15] T HOMAS J. S CHAEFER: The complexity of satisfiability problems. In Proc. 10th STOC, pp.
216–226. ACM Press, 1978. [doi:10.1145/800133.804350] 3
[16] 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] 4
[17] U RI Z WICK: Approximation algorithms for constraint satisfaction problems involving at most three
variables per constraint. In Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’98),
pp. 201–210. ACM Press, 1998. ACM DL. 3
AUTHORS
Venkatesan Guruswami
Professor
Carnegie Mellon University, Pittsburgh, PA
guruswami cmu edu
http://www.cs.cmu.edu/~venkatg
Euiwoong Lee
Graduate student
Carnegie Mellon University, Pittsburgh, PA
euiwoonl cs cmu edu
http://www.cs.cmu.edu/~euiwoonl
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 23
V ENKATESAN G URUSWAMI AND E UIWOONG L EE
ABOUT THE AUTHORS
V ENKATESAN G URUSWAMI, or Venkat, as his colleagues call him, received his Bachelor’s
degree from the Indian Institute of Technology at Madras in 1997. Venkat received his
Ph. D. from the Massachusetts Institute of Technology in 2001. He was fortunate to be
advised by Madhu Sudan, with whom he enjoyed collaboration on a number of topics,
most notably on list decoding.
Since 2008, Venkat has been on the faculty of the Computer Science Department at
Carnegie Mellon University. Earlier, he was a faculty member at the University of
Washington. Venkat was a Miller Research Fellow at UC Berkeley during 2001-02, a
member of the School of Mathematics, Institute for Advanced Study during 2007-08,
and a visiting researcher at Microsoft Research New England during January–June 2014.
Venkat is interested in several topics in theoretical computer science, including algorith-
mic and algebraic coding theory, approximability of fundamental optimization problems,
pseudorandomness, PCPs, and computational complexity theory.
Venkat currently serves on the editorial boards of the Journal of the ACM, the SIAM
Journal on Computing, and the journal Research in the Mathematical Sciences, and was
previously on the editorial boards of the IEEE Transactions on Information Theory, and
is the Editor-in-Chief of the ACM Transactions on Computation Theory. He was recently
Program Committee chair for the 2015 Foundations of Computer Science conference and
the 2012 Computational Complexity Conference. Venkat is a recipient of the Presburger
award, Packard Fellowship, Sloan Fellowship, NSF CAREER award, ACM’s Doctoral
Dissertation Award, and the IEEE Information Theory Society Paper Award.
In his (sadly limited) spare time, Venkat enjoys traveling, ethnic vegetarian food, racquet
sports, and listening to Carnatic music.
E UIWOONG L EE is a Ph. D. student in computer science at Carnegie Mellon University,
advised by Venkat Guruswami. He is interested in various aspects of approximation
algorithms, including hardness of approximation and the power of LP / SDP hierarchies.
After graduating from high school in Seoul, South Korea, he moved to the U. S. and
received a B. S. and an M. S. degrees from Caltech. He enjoys playing and watching
basketball.
T HEORY OF C OMPUTING, Volume 13 (3), 2016, pp. 1–24 24