Near-Optimal UGC-hardness of Approximating Max k-CSPR
Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan

arXiv:1511.06558v1 [cs.CC] 20 Nov 2015

University of California, Berkeley
{pasin,preetum,luca}@berkeley.edu

Abstract
In this paper, we prove an almost-optimal hardness for Max k-CSPR based on Khot’s Unique Games
Conjecture (UGC). In Max k-CSPR , we are given a set of predicates each of which depends on exactly
k variables. Each variable can take any value from 1, 2, . . . , R. The goal is to find an assignment to
variables that maximizes the number of satisfied predicates.
Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max k-CSPR
to within factor 2O(k log k) (log R)k/2 /Rk−1 for any k, R. To the best of our knowledge, this result improves
on all the known hardness of approximation results when 3 ≤ k = o(log R/ log log R). In this case, the
previous best hardness result was NP-hardness of approximating within a factor O(k/Rk−2 ) by Chan.
When k = 2, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and
O’Donnell.
In addition, by extending an algorithm for Max 2-CSPR by Kindler, Kolla and Trevisan, we provide
an Ω(log R/Rk−1 )-approximation algorithm for Max k-CSPR . This algorithm implies that our inapproximability result is tight up to a factor of 2O(k log k) (log R)k/2−1 . In comparison, when 3 ≤ k is a constant,
the previously known gap was O(R), which is significantly larger than our gap of O(polylog R).
Finally, we show that we can replace the Unique Games Conjecture assumption with Khot’s d-to-1
Conjecture and still get asymptotically the same hardness of approximation.

1

1

Introduction

Maximum Constraint Satisfaction Problem (Max CSP) is an optimization problem where the inputs are
a set of variables, an alphabet set, and a set of predicates. Each variable can be assigned any alphabet
from the alphabet set and each predicate depends only on the assignment to a subset of variables. The
goal is to find an assignment to the variables that maximizes the number of satisfied predicates.
Many natural optimization problems, such as Max Cut, Max k-CUT and Max k-SAT, can be formulated as Max CSP. In addition, Max CSP has been shown to help approximate other seemingly-unrelated
problems such as Densest k-Subgraph [CHK11]. Due to this, Max CSP has long been researched by
the approximation algorithm community [Tre98, Has05, CMM09, MM14, KKT15, GM15]. Furthermore,
its relation to PCPs ensures that Max CSP is also well-studied on the hardness of approximation
side [ST00, Eng05, ST06, KKMO07, AM08, GR08, EH08, Cha13].
The main focus of this paper is on Max k-CSPR , a family of Max CSP where the alphabet set is of size
R and each predicate depends on only k variables. On the hardness of approximation side, most early
works focused on boolean Max k-CSP. Samorodnitsky
and Trevisan first showed that Max k-CSP2 is
√
NP-hard to approximate to within factor 2O( k) /2k [ST00]. Engebretsen and Holmerin
later improved
√
√
O( k)
k
constant factors in the exponent O( k) but still yielded hardness of a factor 2
/2 [EH08]. To break
this barrier, Samorodnitsky and Trevisan proved a hardness of approximation conditioned on Khot’s
Unique Games Conjecture (UGC), which will be discussed in more detail later; they achieved a ratio of
O(k/2k ) hardness, which is tight up to a constant for the boolean case [ST06]. Chan later showed that
NP-hardness of approximation at this ratio can be achieved unconditionally and, thus, settled down the
approximability of Max k-CSP2 [Cha13].
Unlike the boolean case, the approximability
of Max k-CSPR when R > 2 is still not resolved. In
√
this case, Engebretsen showed RO( k) /Rk NP-hardness of approximation [Eng05]. Under the Unique
Games Conjecture, a hardness of approximation of O(kR/Rk−1 ) factor was proven by Austrin and
Mossel [AM08] and, independently, by Guruswami and Raghavendra [GR08]. For the case k = 2, results
by Khot et al. [KKMO07] implicitly demonstrate UGC-hardness of approximation within O(log R/R),
made explicit in [KKT15]. Moreover, Austrin and Mossel proved UGC-hardness of approximation of
O(k/Rk−1 ) for infinitely many ks [AM08], but in the regime k ≥ R. Recently, Chan was able to remove
the Unique Game Conjecture assumption from these results [Cha13]. More specifically, Chan showed
NP-hardness of approximation of factor O(kR/Rk−1 ) for every k, R and that of factor O(k/Rk−1 ) for
every k ≥ R. Due to an approximation algorithm with matching approximation ratio by Makarychev
and Makarychev [MM14], Chan’s result established tight hardness of approximation for k ≥ R. On the
other hand, when k < R, Chan’s result gives O(kR/Rk−1 ) hardness of approximation whereas the best
known approximation algorithm achieves only Ω(k/Rk−1 ) approximation ratio [MM14, GM15]. In an
attempt to bridge this gap, we prove the following theorem.
Theorem 1 (Main Theorem) Assuming the Unique Games Conjecture, it is NP-hard to approximate
Max k-CSPR to within 2O(k log k) (log R)k/2 /Rk−1 factor, for any k ≥ 2 and any sufficiently large R.
When k = o(log R/ log log R), our result improves upon the previous best known hardness of approximation result in this regime, due to Chan. In particular, when k is constant, our results are tight up to
a factor of O(polylog R). While Chan’s results hold unconditionally, our result, similar to many of the
aforementioned results (e.g. [ST06, AM08, GR08]), rely on the Unique Games Conjecture.
A unique game is a Max 2-CSP instance where each constraint is a permutation. The Unique Games
Conjecture (UGC), first proposed by Khot in his seminal paper in 2002 [Kho02], states that, for any
sufficiently small η, γ > 0, it is NP-hard to distinguish a unique game where at least 1 − η fraction of constraints can be satisfied from a unique game where at most γ fraction of constraints can be satisfied. The
UGC has since made a huge impact in hardness of approximation; numerous hardness of approximation
results not known unconditionally can be derived assuming the UGC. More surprisingly, UGC-hardness
of approximation for various problems, such as Max Cut [KKMO07], Vertex Cover [KR08] and any

2

Range of k, R
k=2
3≤k<R
R≤k
Any k, R

NP-Hardness


√R
O log
R

k
O Rk−2

k
O Rk−1
–

UGC-Hardness


O logRR
–
–
O(k log k)

2

(log R)
Rk−1

k/2

Approximation


Ω logRR

k
Ω Rk−1

k
Ω Rk−1


log R
Ω R
k−1

References
[Cha13, KKMO07, KKT15]
[Cha13, MM14, GM15]
[Cha13, MM14]
this work

Figure 1: Comparison between our work and previous works. We list the previous best known results
alongside our results. From previous works, there is either an NP-hardness or a UGC-hardness result
matching the best known approximation algorithm in every case except when 3 ≤ k < R. Our hardness
result improves on the best known hardness result when k = o(log R/ log log R), and our approximation
algorithm improves on the previously known algorithm when k = o(log R).
Max CSP [Rag08]1 , are known to be tight. For more details on UGC and its implications, we refer
interested readers to Khot’s survey [Kho10] on the topic.
Another related conjecture from [Kho02] is the d-to-1 Conjecture. In the d-to-1 Conjecture, we consider
d-to-1 games instead of unique games. A d-to-1 game is an instance of Max 2-CSP where the constraint
graph is bipartite. Moreover, each constraint must be a d-to-1 function, i.e., for each assignment to a
variable on the right, there exists d assignments to the corresponding variable on the left that satisfy the
constraint. The d-to-1 Conjecture states that, for any sufficiently small γ > 0, it is NP-hard to distinguish
between a fully satisfiable d-to-1 game and a d-to-1 game where at most γ fraction of constraints can be
satisfied. Currently, it is unknown whether the d-to-1 Conjecture implies the Unique Games Conjecture
and vice versa.
While the d-to-1 Conjecture has yet to enjoy the same amount of influence as the UGC, it has been proven
successful in providing a basis for hardness of graph coloring problems [DMR09, DS10, GS11] and for
Max 3-CSP with perfect completeness [OW09b, Tan09]. Here we show that, by assuming the d-to-1
Conjecture instead of UGC, we can get a similar hardness of approximation result for Max k-CSPR as
stated below.
Theorem 2 Assuming the d-to-1 Games Conjecture holds for some d, it is NP-hard to approximate
Max k-CSPR to within 2O(k log k) (log R)k/2 /Rk−1 factor, for any k ≥ 2 and any sufficiently large R.
As mentioned earlier, there has also been a long line of works in approximation algorithms for Max
k-CSPR . In the boolean case, Trevisan first showed a polynomial-time approximation algorithm with
approximation ratio 2/2k [Tre98]. Hast later improved the ratio to Ω(k/(2k log k)) [Has05]. Charikar,
Makarychev and Makarychev then came up with an Ω(k/2k )-approximation algorithm [CMM09]. As
stated when discussing hardness of approximation of Max k-CSP2 , this approximation ratio is tight up
to a constant factor.
For the non-boolean case, Charikar, Makarychev, and Makarychev’s algorithm achieve Ω(k log R/Rk )
ratio for Max k-CSPR . Makarychev, and Makarychev later improved the approximation ratio to
Ω(k/Rk−1 ) when k = Ω(log R) [MM14]. Additionally, the algorithm was extended by Goldshlager and
Moshkovitz to achieve the same approximation ratio for any k, R [GM15]. On this front, we show the
following result.
Theorem 3 There exists a polynomial-time Ω(log R/Rk−1 )-approximation algorithm for Max k-CSPR .
In comparison to the previous algorithms, our algorithm gives better approximation ratio than all the
known algorithms when k = o(log R). We remark that our algorithm is just a simple extension of Kindler,
Kolla and Trevisan’s polynomial-time Ω(log R/R)-approximation algorithm for Max 2-CSPR [KKT15].
1 Raghavendra showed in [Rag08] that it is hard to approximate any Max CSP beyond what a certain type of semidefinite
program can achieve. However, determining the approximation ratio of a semidefinite program is still not an easy task. Typically,
one still needs to find an integrality gap for such a program in order to establish the approximation ratio.

3

1.1

Summary of Techniques

Our reduction from Unique Games to Max k-CSPR follows the reduction of [KKMO07] for Max 2-CSPs.
We construct a k-query PCP using a Unique-Label-Cover “outer verifier”, and then design a k-query Long
Code test as an “inner verifier”. For simplicity, let us think of k as a constant. We essentially construct a
k-query Dictator-vs.-Quasirandom test for functions f : [R]n → [R], with completeness Ω(1/(log R)k/2 )
and soundness O(1/Rk−1 ). Our test is structurally similar to the 2-query “noise stability” tests of
[KKMO07]: first we pick a random z ∈ [R]n , then we pick k weakly-correlated queries x(1) , . . . , x(k) by
choosing each x(i) ∈ [R]n as a noisy copy of z, i.e., each coordinate (x(i) )j is chosen as zj with some
probability ρ or uniformly at random otherwise. We accept iff f (x(1) ) = f (x(2) ) = · · · = f (x(k) ). The
key technical step is our analysis of the soundness of this test. We need to show that if f is a balanced
function with small low-degree influences, then the test passes with probability O(1/Rk−1 ). Intuitively,
we would like to say that for high enough noise, the values f (x(i) ) are roughly independent and uniform,
so the test passes with probability around 1/Rk−1 . To formalize this intuition, we utilize the Invariance
Principle and Hypercontractivity.
More precisely, if we let f i (x) : [R]n → {0, 1} be the indicator function for f (x) = i, then the test accepts
iff f i (x(1) ) = · · · = f i (x(k) ) = 1 for some i ∈ [R]. For each i ∈ [R], this probability can be written as
the expectation of the product: E[f i (x(1) )f i (x(2) ) . . . f i (x(k) )]. Since x(i) ’s are chosen as noisy copies of
z, this expression is related to the k-th norm of a noisy version of f i . Thus, our problem is reduced to
bounding the k-norm of a noisy function fei : [R]n → [0, 1], which has bounded one-norm E[fei ] = 1/R
since f is balanced. To arrive at this bound, we first apply the Invariance Principle, which essentially
states that a low-degree low-influence function on [R]n behaves on random input similarly to its “boolean
analog” over domain {±1}nR . Here “boolean analog” refers to the function over {±1}nR with matching
Fourier coefficients.
Roughly speaking, now that we have transfered to the boolean domain, we are left to bound the k-norm of
a noisy function on {±1}nR based on its one-norm. This follows from Hypercontractivity in the boolean
setting, which bounds a higher norm of any noisy function on boolean domain in terms of a lower norm.
The description above hides several technical complications. For example, when we pass from a function
[R]n → [0, 1] to its “boolean analog” {±1}nR → R, the range of the resulting function is no longer
bounded to [0, 1]. This, along with the necessary degree truncation, means we must be careful when
bounding norms. Further, Hypercontractivity only allows us to pass from k-norms to (1 + ε)-norms for
small ε, so we cannot use the known 1-norm directly. For details on how we handle these issues, see
Section 3. This allows us to prove soundness of our dictator test without passing through results on
Gaussian space, as was done to prove the “Majority is Stablest” conjecture [MOO10] at the core of the
[KKMO07] 2-query dictator test.
To extend our result to work with d-to-1 Games Conjecture in place of UGC, we observe that our proof
goes through even when we assume a conjecture weaker than the UGC, which we name the One-Sided
Unique Games Conjecture. The only difference between the original UGC and the One-Sided UGC is
that the completeness in UGC is allowed to be any constant smaller than one but the completeness is
a fixed constant for the One-Sided UGC. The conjecture is formalized as Conjecture 3. We show that
the d-to-1 Games Conjecture also implies the One-Sided UGC, which means that our inapproximability
result for Max k-CSPR also holds when we change our assumption to d-to-1 Games.
Lastly, for our approximation algorithm, we simply extend the Kindler, Kolla and Trevisan’s algorithm
by first creating an instance of Max 2-CSPR from Max k-CSPR by projecting each constraint to all
possible subsets of two variables. We then use their algorithm to approximate the instance. Finally, we
set our assignment to be the same as that from KKT algorithm with some probability. Otherwise, we pick
the assignment uniformly at random from [R]. As we shall show in Section 4, with the right probability,
this technique can extend not only the KKT algorithm but any algorithm for Max k′ -CSPR to an
algorithm for Max k-CSPR where k > k′ with some loss in the advantage over the naive randomized
algorithm.

4

1.2

Organization of the Paper

In Section 2, we define notations and list background knowledge that will be used throughout the paper.
Next, we prove our hardness of approximation results, i.e., Theorem 1 and Theorem 2, in Section 3. In
Section 4, we show how to extend Kindler et al.’s algorithm to Max k-CSPR and prove Theorem 3. We
also explicitly present the dictator test that is implicit in our hardness proof, in Section 5. Finally, in
Section 6, we discuss interesting open questions and directions for future works.

2

Preliminaries

In this section, we list notations and previous results that will be used to prove our results.

2.1

Max k-CSPR

We start by giving a formal definition of Max k-CSPR , which is the main focus of our paper.
Definition 1 (Max k-CSPR ) An instance (X , C) of (weighted) Max k-CSPR consists of
• A set X = {x1 , . . . , xn } of variables.
• A set C = {C1 , . . . ,P
Cm } of constraints. Each constraint Ci is a triple (Wi , Si , Pi ) of a positive weight
m
Wi > 0 such that
Wi = 1, a subset of variables Si ⊆ X , and a predicate Pi : [R]Si → {0, 1}
i=1
that maps each assignment to variables in Si to {0, 1}. Here we use [R]Si to denote the set of all
functions from Si to [R], i.e., [R]Si = {ψ : Si → [R]}.
For each assignment of variables ϕ
P: mX → [R], we define its value to be the total weights of the predicates
Wi Pi (ϕ |Si ). The goal is to find an assignment ϕ : X → [R] that
satisfied by this assignment, i.e.,
i=1
with maximum value. We sometimes call the optimum the value of (X , C).
Note that, while the standard definition of Max k-CSPR refers to the unweighted version where W1 =
· · · = Wm = 1/m, Crescenzi, Silvestri and Trevisan showed that the approximability of these two cases
are essentially the same [CST01].2 Hence, it is enough for us to consider just the weight version.

2.2

Unique Games and d-to-1 Conjectures

In this subsection, we give formal definitions for unique games, d-to-1 games and Khot’s conjectures
about them. First, we give a formal definition of unique games.
Definition 2 (Unique Game) A unique game (V, W, E, N, {πe }e∈E ) consists of
• A bipartite graph G = (V, W, E).
• Alphabet size N .
• For each edge e ∈ E, a permutation πe : [N ] → [N ].
For an assignment ϕ : V ∪ W → [N ], an edge e = (v, w) is satisfied if πe (ϕ(v)) = ϕ(w). The goal is to
find an assignment that satisfies as many edges as possible. We define the value of an instance to be the
fraction of edges satisfied in the optimum solution.
The Unique Games Conjecture states that it is NP-hard to distinguish an instance of value close one
from that of value almost zero. More formally, it can be stated as follows.
2 More specifically, they proved that, if the weighted version is NP-hard to approximate to within ratio r, then the unweighted
version is also NP-hard to approximate to within r − on (1) where on (1) represents a function such that on (1) → 0 as n → ∞.

5

Conjecture 1 (Unique Games Conjecture) For any sufficiently small η, γ, it is NP-hard to distinguish a unique game of value at least 1 − η from that of value at most γ.
Next, we define d-to-1 games, which is similar to unique games except that each constraint is a d-to-1
function instead of a permutation.
Definition 3 (d-to-1 Game) A d-to-1 game (V, W, E, N, {πe }e∈E ) consists of
• A bipartite graph G = (V, W, E).
• Alphabet size N .
• For each edge e ∈ E, a function πe : [N ] → [N/d] such that |πe−1 (σ)| = d for every σ ∈ [N/d].
Satisfiability of an edge, the goal, and an instance’s value of is defined similar to that of unique games.
In contrast to the UGC, d-to-1 Conjecture requires perfect completeness, i.e., it states that we cannot
distinguish even a full satisfiable d-to-1 game from one with almost zero value.
Conjecture 2 (d-to-1 Conjecture) For any sufficiently small γ, it is NP-hard to distinguish a d-to-1
game of value 1 from that of value at most γ.

2.3

Fourier Expansions

For any function g : [q]n → R over a finite alphabet [q], we define the Fourier expansion of g as follows.
Consider the space of all functions [q] → R, with the inner-product hu, vi := Ex∈[q] [u(x)v(x)], where the
expectation is over a uniform x ∈ [q]. Pick an orthonormal basis l1 , . . . , lq for this space li : Σ → R, such
that l1 is the constant function 1. We can now write g in the tensor-product basis, as
g(x1 , x2 , . . . , xn ) =

X

s∈[q]n

ĝ(s) ·

n
Y

ls(i) (xi ).

(1)

i=1

Since we pick l1 (x) = 1 for all x ∈ [q], we also have Ex∈[q] [li (x)] = hli , l1 i = 0 for every i 6= 1.
Throughout, we use ĝ to refer to the Fourier coefficients of a function g.
For functions g : [q]n → R, the p-norm is defined as
p 1/p
E [|g(x)| ] .

||g||p =

(2)

x∈[q]n

In particular, the squared 2-norm is
||g||22 =

2.3.1

2
E n [g(x) ] =

x∈[q]

X

ĝ(s)2 .

(3)

s∈[q]n

Noise Operators
ρ

For x ∈ [q]n , let y ← x denote that y is a ρ-correlated copy of x. That is, each coordinate yi is
independently chosen to be equal to xi with probability ρ, or chosen uniformly at random otherwise.
Define the noise operator Tρ acting on any function g : [q]n → R as
(Tρ g)(x) = E [g(y)].

(4)

ρ

y ←x

Notice that the noise operator Tρ acts on the Fourier coefficients on this basis as follows.
f (x) = Tρ g(x) =

X

s∈[q]n

ĝ(s) · ρ|s| ·

where |s| is defined as |{i | s(i) 6= 1}|.

6

n
Y
i=1

ls(i) (xi )

(5)

2.3.2

Degree Truncation

For any function g : [q]n → R, let g ≤d denote the (≤ d)-degree part of g, i.e.,
g

≤d

X

(x) =

s∈[q]n ,|s|≤d

ĝ(s) ·

n
Y

ls(i) (xi ),

(6)

i=1

and similarly let g >d : [q]n → R denote the (> k)-degree part of g, i.e.,

X

g >d (x) =

s∈[q]n ,|s|>d

ĝ(s) ·

n
Y

ls(i) (xi ).

(7)

i=1

Notice that degree-truncation commutes with the noise-operator, so writing Tρ g ≤d is unambiguous.
Also, notice that truncating does not increase 2-norm:
||g ≤d ||22 =

X

s∈[q]n ,|s|≤d

ĝ(s)2 ≤

X

s∈[q]n

ĝ(s)2 = ||g||22 .

(8)

We frequently use the fact that noisy functions have small high-degree contributions. That is, for any
function g : [q]n → [0, 1], we have
||Tρ g >d ||22 =

2.3.3

X

s∈[q]n ,|s|>d

ρ2|s| ĝ(s)2 ≤ ρ2d

X

s∈[q]n

ĝ(s)2 = ρ2d ||g||22 ≤ ρ2d .

(9)

Influences

For any function g : [q]n → R, the influence of coordinate i ∈ [n] is defined as
Infi [g] =

E [V arxi ∈[q] [g(x) | {xj }j6=i ]].

x∈[q]n

(10)

This can be expressed in terms of the Fourier coefficients of g as follows:

X

Infi [g] =

ĝ(s)2 .

(11)

s∈[q]n : s(i)6=1

Further, the degree-d influences are defined as
Infi≤d [g] = Infi [g ≤d ] =

X

ĝ(s)2 .

(12)

s∈[q]n :
|s|≤d, s(i)6=1

2.3.4

Binary Functions

The previous discussion of Fourier analysis can be applied to boolean functions, by specializing to q =
2. However, in this case the Fourier expansion can be written in a more convenient form. Let G :
{+1, −1}n → R be a boolean function over n bits. We can choose orthonormal basis functions l1 (y) = 1
and l2 (y) = y, so G can be written as
G(y) =

X

S⊆[n]

for some coefficients Ĝ(S).

7

Ĝ(S)

Y
i∈S

yi

(13)

Degree-truncation then results in

X

G≤d (y) =

Ĝ(S)

Y

yi ,

(14)

i∈S

S⊆[n]:|S|≤d

and the noise-operator acts as follows:

X

Tρ G(y) =

Ĝ(S)ρ|S|

yi .

(15)

i∈S

S⊆[n]

2.3.5

Y

Boolean Analogs

To analyze k-CSPR , we will want to translate between functions over [R]n to functions over {±1}nR .
The following notion of boolean analogs will be useful.
For any function g : [R]n → R with Fourier coefficients ĝ(s), define the boolean analog of g to be a
function {g} : {±1}n×R → R such that
{g}(z) =
Note that

X

s∈[R]n

||g||22 =

and that

ĝ(s) ·

X

s∈[R]n

Y

zi,s(i) .

(16)

i∈[n],s(i)6=1

ĝ(s)2 = ||{g}||22 ,

{g ≤d } = {g}≤d .

(17)

(18)

Moreover, the noise operator acts nicely on {g} as follows:
Tρ {g} = {Tρ g}.

(19)

For simplicity, we use Tρ to refer to both boolean and non-boolean noise operators with correlation ρ.

2.4

Invariance Principle and Mollification Lemma

We start with the Invariance Principle in the form of Theorem 3.18 in [MOO10]:
Theorem 4 (General Invariance Principle [MOO10]) Let f : [R]n → R be any function such that
V ar[f ] ≤ 1, Infi [f ] ≤ δ, and deg(f ) ≤ d. Let F : {±1}nR → R be its boolean analog: F = {f }. Consider
any “test-function” ψ : R → R that is C 3 , with bounded 3rd-derivative |ψ ′′′ | ≤ C everywhere. Then,
E
y∈{±1}nR

[ψ(F (y))] −

√
d d/2
δ.
E n [ψ(f (x))] ≤ C10 R

(20)

x∈[R]

Note that the above version follows directly
from Theorem 3.18 and Hypothesis 3 of [MOO10], and the
√
fact that uniform ±1 bits are (2, 3, 1/ 2)-hypercontractive as described in [MOO10].
As we shall see later, we will want to apply the Invariance Principle for some functions ψ that are not in
C 3 . However, these functions will be Lipschitz-continuous with some constant c ∈ R (or “c-Lipschitz”),
meaning that
|ψ(x + ∆) − ψ(x)| ≤ c|∆| for all x, ∆ ∈ R.
(21)

e that is that is C 3 ,
Therefore, similar to Lemma 3.21 in [MOO10], we can “smooth” it to get a function ψ
and has arbitrarily small pointwise difference to ψ.
Lemma 1 (Mollification Lemma [MOO10]) Let ψ : R → R be any c-Lipschitz function. Then for
e : R → R such that
any ζ > 0, there exists a function ψ

8

e ∈ C3,
• ψ
e − ψ||∞ ≤ ζ, and,
• ||ψ
e′′′ ||∞ ≤ Cc
e 3 /ζ 2 .
• ||ψ

e not depending on ζ, c.
For some universal constant C,

For completeness, the full proof of the lemma can be found in Appendix A.1.
Now we state the following version of the Invariance Principle, which will be more convenient to invoke.
It can be proved simply by just combining the two previous lemmas. We list a full proof in Appendix A.2.
Lemma 2 (Invariance Principle) Let ψ : R → R be one of the following functions:
1. ψ1 (t) := |t|,
2. ψk (t) :=

k
t
0

1

if t ∈ [0, 1],
if t < 0,
if t ≥ 1.

Let f : [R]n → [0, 1] be any function with all Infi≤d [f ] ≤ δ. Let F : {±1}nR → R be its boolean analog:
F = {f }. Let f ≤d : [R]n → R denote f truncated to degree d, and similarly for F ≤d : {±1}nR → R.
Then, for parameters d = 10k log R and δ = 1/(R10+100k log(R) ), we have

E
y∈{±1}nR

2.5

[ψ(F ≤d (y))] −

k
≤d
E [ψ(f (x))] ≤ O(1/R ).

(22)

x∈[R]n

Hypercontractivity Theorem

Another crucial ingredient in our proof is the hypercontractivity lemma, which says that, on {±1}n
domain, the operator Tρ smooths any function so well that the higher norm can be bound by the lower
norm of the original (unsmoothed) function. Here we use the version of the theorem as stated in [O’D14].
Theorem 5 (Hypercontractivity Theorem [O’D14]) Let 1 ≤ p ≤ q ≤ ∞. For any ρ ≤
n

for any function h : {±1} → R, the following inequality holds:
||Tρ h||q ≤ ||h||p .

p

In particular, for choice of parameter ρ = 1/

q

p−1
q−1

and

(23)

(k − 1) log R, we have

||T2ρ h||k ≤ ||h||1+ε .

(24)

where ε = 4/ log(R).

3

Inapproximability of Max k-CSPR

In this section, we prove Theorem 1 and Theorem 2. Before we do so, we first introduce a conjecture,
which we name One-Sided Unique Games Conjecture. The conjecture is similar to UGC except that the
completeness parameter ζ is fixed in contrast to UGC where the completeness can be any close to one.
Conjecture 3 (One-Sided Unique Games Conjecture) There exists ζ < 1 such that, for any sufficiently small γ, it is NP-hard to distinguish a unique game of value at least ζ from that of value at most
γ.

9

It is obvious that the UGC implies One-Sided UGC with ζ = 1 − η for any sufficiently small η. It is
also not hard to see that, by repeating each alphabet on the right d times and spreading each d-to-1
constraint out to be a permutation, d-to-1 Games Conjecture implies One-Sided UGC with ζ = 1/d. A
full proof of this can be found in Appendix B.
Since both UGC and d-to-1 Games Conjecture imply One-Sided UGC, it is enough for us to show the
following theorem, which implies both Theorem 1 and Theorem 2.
Theorem 6 Unless the One-Sided Unique Games Conjecture is false, for any k ≥ 2 and any sufficiently
large R, it is NP-hard to approximate Max k-CSPR to within 2O(k log k) (log R)k/2 /Rk−1 factor.
The theorem will be proved in Subsection 3.3. Before that, we first prove an inequality that is the heart
of our soundness analysis in Subsection 3.2.

3.1

Parameters

We use the following parameters throughout, which we list for convenience here:

p

• Correlation: ρ = 1/ (k − 1) log R
• Degree: d = 10k log R
• Low-degree influences: δ = 1/(R10+100k log(R) )

3.2

Hypercontractivity for Noisy Low-Influence Functions

Here we show a version of hypercontractivity for noisy low-influence functions over large domains. Although hypercontractivity does not hold in general for noisy functions over large domains, it turns out
to hold in our setting of high-noise and low-influences. The main technical idea is to use the Invariance
Principle to reduce functions over larger domains to boolean functions, then apply boolean hypercontractivity.
Lemma 3 (Main Lemma) Let g : [R]n → [0, 1] be any function with Ex∈[R]n [g(x)] = 1/R. Then, for
our choice of parameters ρ, d, δ: If Infi≤d [g] ≤ δ for all i, then
k
O(k)
/Rk .
E [(Tρ g(x)) ] ≤ 2

x∈[R]n

Before we present the full proof, we outline the high-level steps below. Let f = Tρ g, and define boolean
analogs G = {g}, and F = {f }. Let ψk : R → R be defined as in Lemma 2. Then,
k
≤d
E [f (x) ] ≈ E[ψk (f (x))]

x∈[R]n

(Lemma 2: Invariance Principle)
(Definition of ψk )
(Definition of F )

≈

(Invariance, etc.)
(Since E[|g|] = 1/R)
Proof.

10

[ψk (F ≤d (y))]

(26)

≤ ||F ≤d ||kk

(27)

=

(28)

=
(Hypercontractivity, for small ε)

E
y∈{±1}nR

(25)

≤

||Tρ G≤d ||kk

||T2ρ T1/2 G≤d ||kk

||T1/2 G≤d ||k1+ε
O(k)

(29)
(30)

≈2

||g||k1

(31)

=2

/R .

(32)

O(k)

k

To establish line (25), first notice that
ψk (f (x)) = ψk (f ≤d (x) + f >d (x)) ≤ ψk (f ≤d (x)) + k|f >d (x)|

(33)

where the last inequality is because the function ψk is k-Lipschitz.
Moreover, since g(x) ∈ [0, 1], we have f (x) ∈ [0, 1], so
f (x)k = ψk (f (x)).

(34)

Thus,
k
E[f (x) ] = E[ψk (f (x))]

≤ E[ψk (f

≤d

= E[ψk (f

≤d

≤ E[ψk (f

≤d

(35)

(x))] + k E[|f

>d

(x))] + k||f

>d

(x))] + k||f

>d

(x)|]

(36)

||1

(37)

||2 .

(38)
(39)

And we can bound the 2-norm of f >d , since f is noisy, we have
||f >d ||22 = ||Tρ g >d ||22 ≤ ρ2d ≤ O(1/R2k ).

(40)

The last inequality comes from our choice of ρ and d.
So line (25) is established:

k
≤d
k
E[f (x) ] ≤ E[ψk (f (x))] + O(k/R ).

(41)

Line (26) follows directly from our version of the Invariance Principle (Lemma 2), for the function ψk :
≤d
E [ψk (f (x))] ≤

x∈[R]n

E
y∈{±1}nR

[ψk (F ≤d (y))] + O(1/Rk ).

(42)

We can now rewrite Ey∈{±1}nR [ψk (F ≤d (y))] as
E
y∈{±1}nR

[ψk (F ≤d (y))] ≤

E

[|F ≤d (y)|k ]

(43)

y∈{±1}nR

= ||F ≤d ||kk

(44)

=

(45)

=

||Tρ G≤d ||kk

||T2ρ T1/2 G≤d ||kk .

(46)
(47)

Now, from the Hypercontractivity Theorem, Equation (24), we have
||T2ρ T1/2 G≤d ||k ≤ ||T1/2 G≤d ||1+ε

(48)

for ε = 4/ log R. This establishes line (30):
||T2ρ T1/2 G≤d ||kk ≤ ||T1/2 G≤d ||k1+ε = E[|T1/2 G≤d (y)|1+ε ]k/(1+ε) .

(49)

To show the remaining steps, we will apply the Invariance Principle once more. Notice that for all
t ∈ R : |t|1+ε ≤ |t| + t2 . Hence, we can derive the following bound:
≤d

E[|T1/2 G

(y)|1+ε ] ≤ E[|T1/2 G≤d (y)|] + E[(T1/2 G≤d (y))2 ]

(Matching Fourier expansion)
(Lemma 2, Invariance Principle)

≤d

= E[|T1/2 G
≤ E[|T1/2 g

11

≤d

(y)|] + E[(T1/2 g

(x)|] + E[(T1/2 g

≤d

≤d

(50)

2

(y)) ]
2

(51)
k

(x)) ] + O(1/R ).

(52)

Here we applied our Invariance Principle (Lemma 2) for the function ψ1 as defined in Lemma 2. We will
bound each of the expectations on the RHS, using the fact that g is balanced, and T1/2 g is noisy.
First,
≤d
>d
E[|T1/2 g (x)|] = E[|T1/2 g(x) − T1/2 g (x)|]

(Triangle Inequality)

≤ E[|T1/2 g(x)|] + E[|T1/2 g
= ||g||1 + ||T1/2 g
≤ ||g||1 + ||T1/2 g

(By our choice of d)

≤ 1/R + (1/2)

>d

>d

d

>d

(x)|]

(53)
(54)

||1

(55)

||2

(56)

= O(1/R).

(57)
(58)

Second,
E[(T1/2 g

≤d

X

(x))2 ] =

(1/2)2|s| ĝ(s)2

(59)

s∈[R]n ,|s|≤d

≤

(Since g ∈ [0, 1])

X

(1/2)2|s| ĝ(s)2

(60)

s∈[R]n

= E[(T1/2 g(x))2 ]

(61)

≤ E[T1/2 g(x)]

(62)

= E[g(x)] = 1/R.

(63)

Finally, plugging these bounds into (52), we find:
||T1/2 G≤d ||k1+ε = E[|T1/2 G≤d (y)|1+ε ]k/(1+ε)

(64)

≤ (O(1/R))

(65)

O(k)

/R

k/(1+ε)

(66)

≤2

/R

k(1−ε)

(67)

=2

k

/R .

(68)

=2

O(k)

(Recall ε = 4/ log R)

k/(1+ε)

O(k)

This completes the proof of the main lemma.

3.3

Reducing Unique Label Cover to Max k-CSPR

Here we reduce unique games to Max k-CSPR . We will construct a PCP verifier that reads k symbols
of the proof (with an alphabet of size R) with the following properties:
• (Completeness) If the unique game has value at least ζ, then the verifier accepts an honest proof
with probability at least c = 1/((log R)k/2 2O(k log k) ).
• (Soundness) If the unique game has value at most γ = 2O(k) δ 2 /(4dRk ), then the verifier accepts
any (potentially cheating) proof with probability at most s = 2O(k) /Rk−1 .
Since each symbol in the proof can be viewed as a variable and each accepting predicate of the verifier can
be viewed as a constraint of Max k-CSPR , assuming the One-sided UGC, this PCP implies NP-hardness
of approximating Max k-CSPR of factor s/c = 2O(k log k) (log R)k/2 /Rk−1 and, hence, establishes our
Theorem 6.

12

3.3.1

The PCP

Given a unique game (V, W, E, n, {πe }e∈E ), the proof is the truth-table of a function hw : [R]n → [R] for
each vertex w ∈ W . By folding, we can assume hw is balanced, i.e. hw takes on all elements of its range
with equal probability: Prx∈[R]n [hw (x) = i] = 1/R for all i ∈ [R]. 3
Notationally, for x ∈ [R]n , let (x ◦ π) denote permuting the coordinates of x as: (x ◦ π)i = xπ(i) . Also,
−1
for an edge e = (v, w), we write πe = πv,w , and define πw,v = πv,w
.
The verifier picks a uniformly random vertex v ∈ V , and k independent uniformly random neighbors of v:
w1 , w2 , . . . , wk ∈ W . Then pick z ∈ [R]n uniformly at random, and let x(1) , x(2) , . . . , x(k) be independent
ρ-correlated noisy copies of z (each coordinate xi chosen as equal to zi w.p. ρ, or uniformly at random
otherwise). The verifier accepts if and only if
hw1 (x(1) ◦ πw1 ,v ) = hw2 (x(2) ◦ πw2 ,v ) = · · · = hwk (x(k) ◦ πwk ,v ).

p

To achieve the desired hardness result, we pick ρ = 1/

3.3.2

(69)

(k − 1) log R.

Completeness Analysis

First, note that that we can assume without loss of generality that the graph is regular on V side.4 Let
the degree of each vertex in V be d.
Suppose that the original unique game has an assignment of value at least ζ. Let us call this assignment
ϕ. The honest proof defines hw at each vertex w ∈ W as the long code encoding of this assignment, i.e.,
hw (x) = xϕ(w) . We can written the verifier acceptance condition as follows:
The verifier accepts ⇔ hw1 (x(1) ◦ πw1 ,v ) = · · · = hwk (x(k) ◦ πwk ,v )
⇔ (x
⇔ (x

(1)

(1)

◦ πw1 ,v )ϕ(w1 ) = · · · = (x
)πw1 ,v (ϕ(w1 )) = · · · = (x

(k)

(k)

◦ πwk ,v )ϕ(wk )

)πwk ,v (ϕ(wk )) .

(70)
(71)
(72)

Observe that, if the edges (v, w1 ), . . . , (v, wk ) are satisfied by ϕ, then πw1 ,v (ϕ(w1 )) = · · · =
πwk ,v (ϕ(wk )) = ϕ(v). Hence, if the aforementioned edges are satisfied and x(1) , . . . , x(k) are not
perturbed at coordinate ϕ(v), then (x(1) )πw1 ,v (ϕ(w1 )) = · · · = (x(k) )πwk ,v (ϕ(wk )) .
For each u ∈ V , let su be the number of satisfied edges touching u. Since w1 , . . . , wk are chosen from the
neighbors of v independently from each other, the probability that the edges (v, w1 ), (v, w2 ), . . . , (v, wk )
are satisfied can be bounded as follows:
Pr

v,w1 ,...,wk

=

X

u∈V

=

X

u∈V

= E

u∈V

[(v, w1 ), . . . , (v, wk ) are satisfied]

(73)

Pr

(74)

w1 ,...,wk

[(v, w1 ), . . . , (v, wk ) are satisfied | v = u] Pr[v = u]

(su /d)k Pr[v = u]



(su /d)k

≥ E [su /d]k .

(75)



(76)
(77)

u∈V

3 More precisely, if the truth-table provided is of some function e
hw : [R]n → [R], we define the “folded” function hw as
hw (x1 , x2 , x3 , . . . xn ) := e
hw (x − (x1 , x1 , . . . , x1 )) + x1 , where the ± is over mod R. Notice that the folded hw is balanced, and
also that folding does not affect dictator functions. Thus we define our PCP in terms of hw , but simulate queries to hw using
the actual proof e
hw .
4 See, for instance, Lemma 3.4 in [KR08].

13

Notice that Eu∈V [su /d] is exactly the value of ϕ, which is at least ζ. As a result,
Pr

v,w1 ,...,wk

[(v, w1 ), . . . , (v, wk ) are satisfied] ≥ ζ k .

Furthermore, it is obvious that the probability that x1 , . . . , xk are not perturbedp
at the coordinate ϕ(v)
k
k k
is ρ . As a result, the PCP accepts with probability at least ζ ρ . When ρ = 1/ (k − 1) log R and ζ is
a constant not depending on k and R, the completeness is 1/((log R)k/2 2O(k log k) ).

3.3.3

Soundness Analysis

Suppose that the unique game has value at most γ = 2O(k) δ 2 /(4dRk ). We will show that the soundness
is 2O(k) /Rk−1 .
Suppose for the sake of contradiction that the probability that the verifier accepts Pr[accept] > t =
2Ω(k) /Rk−1 where Ω(·) hides some large enough constant.
ρ

Let hiw (x) : [R]n → {0, 1} be the indicator function for hw (x) = i and let x ← z denote that x is a
ρ-correlated copy of z. We have
Pr[accept] = Pr[hw1 (x(1) ◦ πw1 ,v ) = · · · = hwk (x(k) ◦ πwk ,v )]
=

X

Pr[i = hw1 (x

(1)

i∈[R]

=

X

i

E[hw1 (x

i∈[R]

(Since wi ’s are independent given v) =

X

i∈[R]

Now define gvi : [R]n → [0, 1] as

E

(1)

◦ πw1 ,v ) = · · · = hwk (x

(k)

(78)

◦ πwk ,v )]

◦ πw1 ,v ) · · · hiwk (x(k) ◦ πwk ,v )]



i
(1)
E [hw1 (x
w1

◦ πw1 ,v )] · · · E

wk

[hiwk (x(k)

(80)



◦ πwk ,v )] .

gvi (x) = E [hiw (x ◦ πw,v )]

(79)

(81)

(82)

w∼v

where w ∼ v denotes neighbors w of v.
We can rewrite Pr[accept] as follows:
Pr[accept] =

X

i

E[gv (x

i∈[R]

(Since x

(j)

’s are independent given z) =

X

i∈[R]

=

X

i∈[R]



= E
v

14

E

"

(1)

E
ρ

)gvi (x(2) ) · · · gvi (x(k) )]

[gvi (x)]k

x←z

#

i
k
E [(Tρ gv (z)) ]

(83)

(84)
(85)

v,z

X

i∈[R]



i
k
E[(Tρ gv (z))  .
z

(86)

Next, notice that

X

i∈[R]



i
k
E[(Tρ gv (z)) ] = E 
z

z

X

(Tρ gvi (z))k 

i∈[R]



≤ E 
z

X

i∈[R]



= E Tρ
z



k 

(87)

Tρ gvi (z) 

(88)

 

(89)

X

gvi (z)

i∈[R]

= E[(Tρ 1)k ] = 1.

k 

(90)

z

Therefore, since Pr[accept] > t, by (86), at least t/2 fraction of vertices v ∈ V have

X

i∈[R]

i
k
E[(Tρ gv (z)) ] ≥ t/2.

(91)

z

For these “good” vertices, there must exist some i ∈ [R] for which
i
k
E[(Tρ gv (z)) ] ≥ t/(2R).

(92)

k
Ω(k)
i
/Rk .
E[(Tρ gv (z)) ] > 2

(93)

z

Then for “good” v and i as above,
z

By Lemma 3 (Main Lemma), this means gvi has some coordinate j for which
Infj≤d [gvi ] > δ

(94)

for our choice of d, δ as defined in Subsection 3.1. Pick this j as the label of vertex v ∈ V .
Now to pick the label of a vertex w ∈ W , define the candidate labels as
Cand[w] = {j ∈ [n] : ∃ i ∈ [R] s.t. Infj≤d [hiw ] ≥ δ/2}.

(95)

Notice that

X

j∈[n]

Infj≤d [hiw ] =

X

s∈[R]n : |s|≤d

|s|ĥiw (s)2 ≤ d

X

s:|s|>0

ĥiw (s)2 = d V ar[hiw ] ≤ d.

(96)

So for each i ∈ [R], the projection hiw can have at most 2d/δ coordinates with influence ≥ δ/2. Therefore
the number of candidate labels is bounded:
|Cand[w]| ≤ 2dR/δ.

(97)

Now we argue that picking a random label in Cand[w] for w ∈ W is in expectation a good decoding. We
will show that if we assigned label j to a “good” v ∈ V , then πv,w (j) ∈ Cand[w] for a constant fraction
−1
of neighbors w ∼ v. Note here that πv,w = πw,v
.
First, since gvi (x) = Ew∼v [hiw (x ◦ πw,v )], the Fourier transform of gvi is related to the Fourier transform
of the long code labels hiw as
ĝvi (s) = E [ĥiw (s ◦ πw,v )].
w∼v

15

(98)

Hence, the influence Infj≤d [gvi ] of being large implies the expected influence Inf ≤d
−1

πv,w (j)

[hiw ] of its neighbor

labels w ∼ v is also large as formalized below.
δ < Infj≤k [gvi ] =

X

ĝvi (s)2

(99)

n

s∈[R]
|s|≤k,sj 6=1

=
≤

X

X

i
2
E [ĥw (s ◦ πw,v ) ]

(101)

X

n

s∈[R]
|s|≤k,sj 6=1

= E [
w∼v

(100)

w∼v

= E [
w∼v

i
2
E [ĥw (s ◦ πw,v )]

w∼v

X

ĥiw (s ◦ πw,v )2 ]
ĥiw (s)2 ]

(103)

ĥiw (s)2 ]

(104)

n

s∈[R]
|s|≤k,s −1

πw,v (j)

−1
(Since πv,w = πw,v
)= E [
w∼v

(102)

X

6=1

s∈[R]n
|s|≤k,sπv,w (j) 6=1

= E [Infπ≤d
[hiw ]]
v,w (j)

(105)

w∼v

[hiw ] ≥ δ/2, and so πv,w (j) ∈
Therefore, at least δ/2 fraction of neighbors w ∼ v must have Infπ≤d
v,w (j)
Cand[w] for at least δ/2 fraction of neighbors of “good” vertices v.
Finally, recall that at least (t/2) fraction of vertices v ∈ V are “good”. These vertices have at least (δ/2)
fraction of neighbors w ∈ W with high-influence labels and the matching label w ∈ W is picked with
probability at least δ/(2dR). Moreover, as stated earlier, we can assume that the graph is regular on V
side. Hence, the expected fraction of edges satisfied by this decoding is at least
(t/2)(δ/2)(δ/2dR) = tδ 2 /(4dR) = 2Ω(k) δ 2 /(4dRk ) > γ,

(106)

which contradicts our assumption that the unique game has value at most γ. Hence, we can conclude
that the soundness is at most 2O(k) /Rk−1 as desired.

4

Ω(log R/Rk−1)-Approximation Algorithm for Max k-CSPR

Instead of just extending the KKT algorithm to work with Max k-CSPs, we will show a more generalized statement that any algorithm that approximates Max CSPs with small arity can be extended
′
to approximate Max CSPs with larger arities. In particular, we show how to extend any f (R)/Rk ′
O(min{k′ ,k−k′ })
k
approximation algorithm for Max k -CSPR to an (f (R)/2
)/R -approximation algorithm
for Max k-CSPR where k > k′ .
Since the naive algorithm that assigns every variable randomly has an approximation ratio of 1/Rk , we
think of f (R) as the advantage of algorithm A over the randomized algorithm. From this perspective,
′
′
our extension lemma preserves the advantage up to a factor of 1/2O(min{k ,k−k }) .
The extension lemma and its proof are stated formally below.
Lemma 4 Suppose that there exists a polynomial-time approximation algorithm A for Max k′ -CSPR
′
that outputs an assignment with expected value at least f (R)/Rk times the optimum. For any k > k′ , we
can construct a polynomial-time approximation algorithm B for Max k-CSPR that outputs an assignment
′
′
with expected value at least (f (R)/2O(min{k ,k−k }) )/Rk times the optimum.

16

Proof. The main idea of theproof is simple. We turn an instance of Max k-CSPR to an instance of Max
′
k′ -CSPR by constructing kk′ Rk−k new constraints for each original constraint; each new constraint is
a projection of the original constraint to a subset of variables of size k′ . We then use A to solve the newly
constructed instance. Finally, B simply assigns each variable with the assignment from A with a certain
probability and assign it randomly otherwise.
For convenience, let α be

k−k′
.
k

We define B on input (X , C) as follows:

′

1. Create an instance (X , C ) of Max k′ -CSPR with the same variables and, for each C = (W, S, P ) ∈ C
′
′
and for every subset S ′ of S with |S ′ | = k′ and every τ ∈ [R]S−S , create a constraint C S ,τ =
′
′
′
′
′
′
S′
W
(W , S , P ) in C where W = k k−k′ and P : [R] → {0, 1} is defined by
(k ′ )R
P ′ (ψ) = P (ψ ◦ τ ).
Here ψ ◦ τ is defined as follows:
ψ ◦ τ (x) =



if x ∈ S ′ ,
otherwise.

ψ(x)
τ (x)

2. Run A on input (X , C ′ ). Denote the output of A by ϕA .
3. For each x ∈ X , with probability α, pick ϕB (x) randomly from [R]. Otherwise, let ϕB (x) be ϕA (x).
4. Output ϕB .
We now show that ϕB has expected value at least (f (R)/2O(min{k

′

,k−k′ })

)/Rk times the optimum.

′

First, observe that the optimum of (X , C ′ ) is at least 1/Rk−k times that of (X , C). To see that this is
true, consider any assignment ϕ : X → [R] and any constraint C = (W, S, P ). Its weighted contribution
in (X , C) is W P (ϕ|S ). On the other hand, k Wk−k′ P (ϕ|S ) appears kk′ times in (X , C ′ ), once for each
(k ′ )R
′
subset S ′ ⊆ S of size k′ . Hence, the value of ϕ with respect to (X , C ′ ) is at least 1/Rk−k times its value
with respect to (X , C)
′

Recall that the algorithm A gives an assignment of expected value at least f (R)/Rk times the optimum
of (X , C ′ ). Hence, the expected value of ϕA is at least f (R)/Rk times the optimum of (X , C).
Next, we will compute the expected value of ϕB (with respect to (X , C)). We start by computing the
expected value of ϕB with respect to a fixed constraint C = (W, S, P ) ∈ C, i.e., EϕB [W P (ϕB |S )]. For
each S ′ ⊆ S of size k, we define DS ′ as the event where, in step 3, ϕB (x) is assigned to be ϕA (x) for all
x ∈ S ′ and ϕB (x) is assigned randomly for all x ∈ S − S ′ .
Since DS ′ is disjoint for all S ′ ⊆ S of size k, we have the following inequality.

X

E [W P (ϕB |S )] ≥

ϕB

′

S ′ ⊆S
|S ′ |=k

′

Pr[DS ′ ] E [W P (ϕB |S ) | DS ′ ]

(107)

ϕB

′

(Since Pr[DS ′ ] = αk−k (1 − α)k ) = αk−k (1 − α)k

′

X

S ′ ⊆S
|S ′ |=k

W E [P (ϕB |S ) | DS ′ ]

(108)

ϕB

Moreover, since every vertex in S − S ′ is randomly assigned when DS ′ occurs, E[P (ϕB |S ) | DS ′ ] can be
′
view as the average value of P ((ϕA |S ′ ) ◦ τ ) over all τ ∈ [R]S−S . Hence, we can derive the following:
E [P (ϕB |S ) | DS ′ ] =

ϕB

1
Rk−k′

As a result, we have
k−k′

E [W P (ϕB |S )] ≥

ϕB

α

(1 − α)
Rk−k′

k′





E 

ϕA



X

τ ∈[R]

  X
E 
ϕA

17

S−S ′



P ((ϕA |S ′ ) ◦ τ ) .

X

S ′ ⊆S τ ∈[R]S−S ′
|S ′ |=k

(109)




W P ((ϕA |S ′ ) ◦ τ ) .

(110)

By summing (110) over all constraints C ∈ C, we arrive at the following inequality.



E 

ϕB

X

C=(W,S,P )∈C

k−k′

≥

=

=

α

(1 − α)
Rk−k′

 



W P (ϕB |S )

k′




E 

ϕA

(111)



X

C=(W,S,P )∈C



X

′
′
k

αk−k (1 − α)k E 
k′
ϕA

S ′ ⊆S τ ∈[R]S−S ′
|S ′ |=k

C=(W,S,P )∈C



 

X

′
′
k
αk−k (1 − α)k E 
k′
ϕA

X

 X




 X





X

S ′ ⊆S τ ∈[R]S−S ′
|S ′ |=k

C ′ =(W ′ ,S ′ ,P ′ )∈C



k
k′

′



W

P ((ϕA |S ′ ) ◦ τ )
Rk−k′



W P (ϕA |S ′ )
′

(112)

W P ((ϕA |S ′ ) ◦ τ )

(113)

(114)



′

′

The first expression is the expected value of ϕB whereas the last is kk′ αk−k (1 − α)k times the expected
value of ϕA . Since the expected value of ϕA is at least f (R)/Rk times the optimum of (X , C), the

′
′
expected value of ϕB is at least ( kk′ αk−k (1 − α)k )(f (R)/Rk ) times the optimum of (X , C).
Finally, we substitute α =

k−k′
k

in to get

 

 

k − k′
k

k−k′ 

k′

′
′
k
αk−k (1 − α)k =
k′

Let l = min{k′ , k − k′ }. We then have

 
k
k′

k − k′
k

k
k′

k′
k

k−k′ 

=

k′
k

 
k
l

k′

k−l
k

 l 

.

k−l  l

k−l
k
l
k


k−l k
≥
k

≥

l
k

k−l  l

= (1 − l/k)2k/l
2l

(From Bernoulli’s inequality and from l ≤ k/2) ≥ 1/2 .

(115)

l
k

2l

(116)
(117)
(118)
(119)
(120)

Hence, ϕB has expected value at least (f (R)/2O(l) )/Rk times the optimum of (X , C), which completes
the proof of this lemma.
Finally, Theorem 3 is an immediate consequence of applying Lemma 4 to the algorithm from [KKT15]
with k′ = 2 and f (R) = Ω(R log R).

5

k-Query Large Alphabet Dictator Test

We remark that the results of Section 3 also implicitly yield a k-query nonadaptive Dictator-vs.Quasirandom test for functions over large alphabet.
A Dictator-vs.-Quasirandom test aims to
distinguish dictator functions from functions with small low-degree influences (“quasirandom”). This
concept was essentially introduced in [Hås96], and we borrow the “quasirandom” terminology from
[OW09a] (adapted here for functions over non-binary alphabets). Specifically, we have the following
test:

18

i
Theorem 7 For any function f : [R]n → [R], and any i ∈ [R], let fp
: [R]n → {0, 1} denote the
indicator function for f (x) = i. For any k, R ≥ 2, set parameters ρ = 1/ (k − 1) log R, d = 10k log R,
and δ = 1/(R10+100k log(R) ). Then there exists a k-query nonadaptive Dictator-vs.Quasirandom test with
the following guarantees:

• (Completeness) If f is a dictator, i.e. f (x) = xj for some coordinate j ∈ [n], then the test passes
with probability at least
ρk = 1/((log R)k/2 2O(k log k) )
• (Soundness) If f has Infj≤d [f i ] ≤ δ for all coordinates j ∈ [n] and all projections i ∈ [R], then
the test passes with probability at most
2O(k) /Rk−1
Notice that if we assume f is balanced, then this theorem is immediately implied by the techniques of
Section 3. However, to extend this to general functions via “folding”, we must technically show that
the operation of folding keeps low-influence functions as low-influence. The full proof can be found in
Appendix C.

6

Conclusions and Open Questions

We conclude by posting interesting open questions regarding the approximability of Max k-CSPR and
providing our opinions on each question. First, as stated earlier, even with our results, current inapproximability results do not match the best known approximation ratio achievable in polynomial time when
3 ≤ k < R. Hence, it is intriguing to ask what the right ratio that Max k-CSPR becomes NP-hard
to approximate is. Since our hardness factor 2O(k log k) (log R)k/2 /Rk−1 does not match Chan’s hardness
factor O(k/Rk−2 ) when k = R, it is likely that there is a k between 3 and R − 1 such that a drastic
change in the hardness factor, and technique that yields that factor, occurs.
Moreover, since our PCP has completeness of 1/(2O(k) (log R)k/2 ), even if one cannot improve on the
inapproximability factor, it is still interesting if one can come up with a hardness result with almost
perfect completeness. √In fact, even for k = 2, there is no known hardness of approximation of factor
better than O(log R/ R) with near perfect completeness whereas the best UGC-hardness known is
O(log R/R).
It is also interesting to try to relax assumptions for other known inapproximability results from UGC
to the One-Sided UGC. Since the One-Sided UGC is implied by d-to-1 Games Conjecture, doing so will
imply inapproximability results based on the d-to-1 Games Conjecture. Moreover, without going into too
much detail, we remark that most attempts to refute the UGC and the d-to-1 Conjecture need the value
of the game to be high [ABS15, CMM06a, CMM06b, GT06, Kho02, Kol11, Tre08]. Hence, these algorithms are not candidates to refute the One-Sided UGC. In addition, Arora, Barak and Steurer’s [ABS15]
subexponential time algorithm for unique games suggest that unique games have intermediate complexity,
meaning that, even if the UGC is true, the UGC-hardness would not imply exponential time lower bounds.
On the other hand, to the best of the authors’ knowledge, the ABS algorithm does not run in subexponential time when the completeness is small. Hence, the One-Sided UGC may require exponential time
to solve, which could give similar running time lower bounds for the resulting hardness of approximation
results. Finally, there are evidences suggesting that relaxing completeness or soundness conditions of a
conjecture can make it easier; the most relevant such result is that from Feige and Reichman who proved
that, if one only cares about the approximation ratio and not completeness and soundness, then unique
game is hard to approximate to within factor ε for any ε > 0 [FR04].

References
[ABS15]

Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games
and related problems. J. ACM, 62(5):42, 2015.

19

[AM08]

P. Austrin and E. Mossel. Approximation resistant predicates from pairwise independence.
In Computational Complexity, 2008. CCC ’08. 23rd Annual IEEE Conference on, pages
249–258, June 2008.

[Cha13]

Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings
of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 447–
456, New York, NY, USA, 2013. ACM.

[CHK11]

Moses Charikar, MohammadTaghi Hajiaghayi, and Howard Karloff. Improved approximation
algorithms for label cover problems. Algorithmica, 61(1):190–206, 2011.

[CMM06a] Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms
for unique games. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory
of Computing, STOC ’06, pages 205–214, New York, NY, USA, 2006. ACM.
[CMM06b] Eden Chlamtac, Konstantin Makarychev, and Yury Makarychev. How to play unique games
using embeddings. In 47th Annual IEEE Symposium on Foundations of Computer Science
(FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 687–696,
2006.
[CMM09]

Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms
for maximum constraint satisfaction problems. ACM Transactions on Algorithms, 5(3), 2009.

[CST01]

Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan. On weighted vs unweighted versions of combinatorial optimization problems. Information and Computation, 167(1):10–26,
2001.

[DMR09]

Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring.
SIAM Journal on Computing, 39(3):843–873, 2009.

[DS10]

Irit Dinur and Igor Shinkar. On the conditional hardness of coloring a 4-colorable graph
with super-constant number of colors. In Proceedings of the 13th International Conference on
Approximation, and 14 the International Conference on Randomization, and Combinatorial
Optimization: Algorithms and Techniques, APPROX/RANDOM’10, pages 138–151, Berlin,
Heidelberg, 2010. Springer-Verlag.

[EH08]

Lars Engebretsen and Jonas Holmerin. More efficient queries in pcps for np and improved
approximation hardness of maximum csp. Random Struct. Algorithms, 33(4):497–514, December 2008.

[Eng05]

Lars Engebretsen. The nonapproximability of non-boolean predicates. SIAM J. Discret.
Math., 18(1):114–129, January 2005.

[FR04]

Uriel Feige and Daniel Reichman. On systems of linear equations with two variables per
equation. In Klaus Jansen, Sanjeev Khanna, JoséD.P. Rolim, and Dana Ron, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,
volume 3122 of Lecture Notes in Computer Science, pages 117–127. Springer Berlin Heidelberg, 2004.

[GM15]

Gil Goldshlager and Dana Moshkovitz.
Approximating kCSP for large alphabets.
https://people.csail.mit.edu/dmoshkov/papers/Approximating%20MAX%20kCSP.pdf,
2015.

[GR08]

Venkatesan Guruswami and Prasad Raghavendra. Constraint satisfaction over a non-boolean
domain: Approximation algorithms and unique-games hardness. In Ashish Goel, Klaus
Jansen, JoséD.P. Rolim, and Ronitt Rubinfeld, editors, Approximation, Randomization and
Combinatorial Optimization. Algorithms and Techniques, volume 5171 of Lecture Notes in
Computer Science, pages 77–90. Springer Berlin Heidelberg, 2008.

[GS11]

Venkatesan Guruswami and Ali Kemal Sinop. The complexity of finding independent sets
in bounded degree (hyper)graphs of low chromatic number. In Proceedings of the TwentySecond Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco,
California, USA, January 23-25, 2011, pages 1615–1626, 2011.

[GT06]

Anupam Gupta and Kunal Talwar. Approximating unique games. In Proceedings of the
Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami,
Florida, USA, January 22-26, 2006, pages 99–106, 2006.

20

[Hås96]

Johan Håstad. Clique is hard to approximate within n1−ε . In Foundations of Computer
Science, 1996. Proceedings., 37th Annual Symposium on, pages 627–636. IEEE, 1996.

[Has05]

Gustav Hast. Approximating Max kCSP - outperforming a random assignment with almost
a linear factor. In Proceedings of the 32Nd International Conference on Automata, Languages
and Programming, ICALP’05, pages 956–968, Berlin, Heidelberg, 2005. Springer-Verlag.

[IP01]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst.
Sci., 62(2):367–375, 2001.

[Kho02]

Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thiryfourth Annual ACM Symposium on Theory of Computing, STOC ’02, pages 767–775, New
York, NY, USA, 2002. ACM.

[Kho10]

Subhash Khot. On the unique games conjecture (invited survey). In Proceedings of the
25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 99–121, 2010.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable csps? SIAM J. Comput., 37(1):319–357,
2007.
[KKT15]

Guy Kindler, Alexandra Kolla, and Luca Trevisan. Approximation of non-boolean 2csp.
CoRR, abs/1504.00681, 2015.

[Kol11]

Alexandra Kolla. Spectral algorithms for unique games.
20(2):177–206, 2011.

[KR08]

Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε.
J. Comput. Syst. Sci., 74(3):335–349, May 2008.

[MM14]

Konstantin Makarychev and Yury Makarychev. Approximation algorithm for non-boolean
max-k-csp. Theory of Computing, 10:341–358, 2014.

[MOO10]

Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions
with low influences: invariance and optimality. Ann. Math. (2), 171(1):295–341, 2010.

[O’D14]

Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.

[OW09a]

Ryan O’Donnell and Yi Wu. 3-bit dictator testing: 1 vs. 5/8. In Proceedings of the Twentieth
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA,
January 4-6, 2009, pages 365–373, 2009.

[OW09b]

Ryan O’Donnell and Yi Wu. Conditional hardness for satisfiable 3-csps. In Proceedings of the
41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA,
May 31 - June 2, 2009, pages 493–502, 2009.

[Rag08]

Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In
Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08,
pages 245–254, New York, NY, USA, 2008. ACM.

[ST00]

Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the Thirty-Second Annual ACM Symposium on
Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 191–199, 2000.

[ST06]

Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and pcps.
In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC
’06, pages 11–20, New York, NY, USA, 2006. ACM.

[Tan09]

Linqing Tang. Conditional hardness of approximating satisfiable max 3csp-q. In Yingfei
Dong, Ding-Zhu Du, and Oscar Ibarra, editors, Algorithms and Computation, volume 5878
of Lecture Notes in Computer Science, pages 923–932. Springer Berlin Heidelberg, 2009.

[Tre98]

Luca Trevisan. Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72–88, 1998.

[Tre08]

Luca Trevisan. Approximation algorithms for unique games. Theory of Computing, 4(1):111–
128, 2008.

21

Computational Complexity,

A

Proofs of Preliminary Results

For completeness, we prove some of the preliminary results, whose formal proofs were not found in the
literature by the authors.

A.1

Mollification Lemma

Below is the proof of the Mollification Lemma. We remark that, while its main idea is explained
in [O’D14], the full proof is not shown there. Hence, we provide the proof here for completeness.
Proof. (of Lemma 1) Let p : R → R be a C 4 function supported only on [−1, +1], such that p(y) forms
2
a probability distribution. (For example, an appropriately normalized version of e−1/(1+y ) for |y| ≤ 1).
Define pλ (y) to be re-scaled to have support [−λ, +λ] for some λ > 0:
pλ (y) := (1/λ)p(y/λ).

(121)

Let Yλ be a random variable with distribution pλ (y), supported on [−λ, +λ]. We will set λ = ζ/c.
Now, define

e := E [ψ(x + Yλ )].
ψ

(122)

Yλ

This is pointwise close to ψ, since ψ is c-Lipschitz:

e − ψ(x)| = | E [ψ(x + Yλ ) − ψ(x)]| ≤ E [|ψ(x + Yλ ) − ψ(x)|] ≤ E [c|Yλ |] ≤ cλ = ζ.
|ψ(x)

(123)

Yλ

Yλ

Yλ

e is C 3 , because ψ(x)
e can be written as a convolution:
Further, ψ

(124)

e′′′ is bounded, for a fixed x ∈ R, define the constant z := ψ(x). Then,
To see that ψ

(125)

e = (ψ ∗ pλ )(x) =⇒ ψe′′′ = (ψ ∗ pλ )′′′ = (ψ ∗ p′′′
ψ(x)
λ ).
e′′′ (x)| = |(ψ ∗ p′′′
|ψ
λ )(x)|

′

(z is constant, so z = 0)

= |(ψ ∗

= |(ψ ∗

p′′′
λ
p′′′
λ

−

−

= |((ψ − z) ∗
=
=
≤
(c-Lipschitz)

Z

Z

Z

′

z ∗ p′′λ )(x)|
z ∗ p′′′
λ )(x)|
′′′
pλ )(x)|

(126)
(127)
(128)

+∞

−∞
+∞
−∞
+λ

−λ

p′′′
λ (y)(ψ(x − y) − z)dy

(129)

p′′′
λ (y)(ψ(x − y) − ψ(x))dy

(130)

|p′′′
λ (y)||ψ(x − y) − ψ(x)|dy

≤ ||p′′′
λ ||∞

Z

+λ

−λ
2

|cy|dy

= ||p′′′
λ ||∞ cλ .

e := ||p′′′ ||∞ . We have
Define the universal constant C

4 e
4 ′′′
′′′
p′′′
λ (y) = (1/λ )p (y/λ) =⇒ ||pλ ||∞ ≤ (1/λ )C.

e′′′ (x)| ≤ Cc
e 3 /ζ 2 , which completes the proof of Lemma 1.
With our choice of λ = ζ/c, this yields |ψ
22

(131)
(132)
(133)

(134)

A.2

Proof of Lemma 2

Below we show the proof of Lemma 2.

e by applying Lemma 1 for
Proof. First, we “mollify” the function ψ to construct a C 3 function ψ,
k
ζ = 1/R . Notice that both choices of ψ are k-Lipschitz. Therefore the Mollification Lemma guarantees
e′′′ (x)| ≤ Ck
e 3 R2k for some universal constant C.
e
that |ψ
e is pointwise close to ψ, with deviation at most 1/Rk , we have
Since ψ
E

y∈{±1}nR

[ψ(F ≤d (y))] −

≤d
E [ψ(f (x))] ≤

x∈[R]n

E

y∈{±1}nR

e ≤d (y))] −
[ψ(F

e ≤d (x))] + O(1/Rk ).
E [ψ(f

x∈[R]n

e we have
Applying the General Invariance Principle (Theorem 4) with the function ψ,
E

y∈{±1}nR

e ≤d (y))] −
[ψ(F

√
e ≤d (x))] ≤ Ck
e 3 R2k 10d Rd/2 δ.
E n [ψ(f

(135)

(136)

x∈[R]

By our choice of parameters d, δ, this is O(1/Rk ).

B d-to-1 Games Conjecture implies One-Sided Unique
Games Conjecture
In this section, we prove that if d-to-1 Games Conjecture is true, then so is One-Sided Unique Games
Conjecture.
Lemma 5 For every d ∈ N, d-to-1 Games Conjecture implies One-Sided UGC.
Proof. Suppose that d-to-1 Games Conjecture is true for some d ∈ N. We will prove One-Sided UGC;
more specifically, ζ in the One-Sided UGC is 1/d. The reduction from a d-to-1 game (V, W, E, N, {πe }e∈E )
to a unique game (V ′ , W ′ , E ′ , N ′ , {πe′ }e∈E ) can be described as follows:
• Let V ′ = V, W ′ = W, E ′ = E, and N ′ = N
• We define πe′ as follows. For each θ ∈ [N/d], let the elements of πe−1 (θ) be σ1 , σ2 , . . . , σd ∈ [N ]. We
then define πe′ (σi ) = d(θ − 1) + i.
Now, we will prove the soundness and completeness of this reduction.
(Completeness) Suppose that the d-to-1 game is satisfiable. Let ϕ : V ∪ W → [N ] be the assignment
that satisfies every constraint in the d-to-1 game. We define ϕ′ : V ′ ∪ W ′ → [N ′ ] by first assign
ϕ′ (v) = ϕ(v) for every v ∈ V . Then, for each w ∈ W , pick ϕ′ (w) to be an assignment that satisfies as
many edges touching w in the unique game as possible, i.e., for a fixed w, ϕ′ (w) is select to maximize
′
|{v ∈ N (w) | π(v,w)
(ϕ(v)) = ϕ′ (w)}| where N (w) is the set of neighbors of w. From how ϕ′ (w) is picked,
we have
d

′
|{v ∈ N (w) | π(v,w)
(ϕ(v)) = ϕ′ (w)}| ≥

1X
′
|{v ∈ N (w) | π(v,w)
(ϕ(v)) = d(ϕ(w) − 1) + i}|.
d

(137)

i=1

′
′
Let 1[π(v,w)
(ϕ(v)) = d(ϕ(w) − 1) + i] be the indicating variable whether π(v,w)
(ϕ(v)) = d(ϕ(w) − 1) + i,
we can rewrite the right hand side as follows:

23

d
1X
′
|{v ∈ N (w) | π(v,w)
(ϕ(v)) = d(ϕ(w) − 1) + i}|
d

(138)

i=1

=

d
1X X
′
1[π(v,w)
(ϕ(v)) = d(ϕ(w) − 1) + i]
d

(139)

i=1 v∈N(w)

=

d
1 X X
′
1[π(v,w)
(ϕ(v)) = d(ϕ(w) − 1) + i].
d

(140)

v∈N(w) i=1

′
′
is defined and since π(v,w) (ϕ(v)) = ϕ(w), there exists i ∈ [d] such that π(v,w)
(ϕ(v)) =
From how π(v,w)
d(ϕ(w) − 1) + i. As a result, we have
d
|N (w)|
1 X X
1 X
′
1=
.
1[π(v,w)
(ϕ(v)) = d(ϕ(w) − 1) + i] ≥
d
d
d
v∈N(w) i=1

(141)

v∈N(w)

In other words, at least 1/d fraction of edges touching w is satisfied in the unique game for every w ∈ W .
Hence, ϕ′ has value at least 1/d, which means that the unique game also has value at least 1/d.
(Soundness) Suppose that the value of the d-to-1 game is at most γ. For any assignment ϕ′ : V ′ ∪ W ′ →
[N ′ ] to the unique game, we can define an assignment ϕ : V ∪ W → [N ] by
ϕ(u) =



ϕ′ (u)
⌊(ϕ′ (u) − 1)/d⌋ + 1

if u ∈ V,
if u ∈ W.

(142)

From how πe′ is defined, it is easy to see that, if πe′ (ϕ′ (v)) = ϕ′ (w), then πe (ϕ(v)) = ϕ(w). In other
words, the value of ϕ′ with respect to the unique game is no more than the value of ϕ with respect to
the d-to-1 game. As a result, the value of the unique game is at most ε.
As a result, if it is NP-hard to distinguish a satisfiable d-to-1 game from one with value at most γ, then
it is also NP-hard to distinguish a unique game of value at least ζ = 1/d from that with value at most
γ, which concludes the proof of this lemma.

C

Proof of Dictator Test

Here we prove our result for the Dictator-vs.-Quasirandom test (Theorem 7).
Proof. (of Theorem 7) For c ∈ [R], define the function
fc (x1 , x2 , . . . , xn ) := f (x1 + c, x2 + c, . . . , xn + c) − c.

(143)

Note that ±c is performed modulo R.
The test works as follows: Pick z ∈ [R]n uniformly at random, and let x(1) , x(2) , . . . , x(k) be independent
ρ-correlated noisy copies of z. Then, pick c1 , c2 , . . . , ck independently uniformly at random, where each
ci ∈ [R]. Accept iff
fc1 (x(1) ) = fc2 (x(2) ) = · · · = fck (x(k) ).
(144)
For completeness, notice that if f is a dictator, then fc = f for all c ∈ [R]. Say f is a dictator on the
j-th coordinate: f (x) = xj . Then the test clearly accepts with probability at least ρk (if none of the
ρ
coordinates j were perturbed in all the noisy copies x(i) ← z).

24

For soundness: For any i ∈ [R], let f i : [R]n → {0, 1} denote the indicator function for f (x) = i, and
similarly for fci : [R]n → {0, 1}. Notice that
fci (x) = f i+c (x + (c, c, . . . , c))

(145)

Then, write the acceptance probability as
Pr[accept] =

Pr

ρ

ci ,z,x(j) ←z

=

X

[fc1 (x(1) ) = fc2 (x(2) ) = · · · = fck (x(k) )]

Pr

ρ

(j) ←z
i∈[R] ci ,z,x

=
(Independence of ci )

=

X

E

ρ
(j) ←z
i∈[R] ci ,z,x

X

E

i∈[R] z,x

ρ

(146)

[i = fc1 (x(1) ) = fc2 (x(2) ) = · · · = fck (x(k) )]

(147)

[fci1 (x(1) )fci2 (x(2) ) . . . fcik (x(k) )]

(148)

[ E [fci1 (x(1) )] E [fci2 (x(2) )] . . . E [fcik (x(k) )]].

(j) ←z c1

c2

(149)

c2

(150)

If we define the function g i : [R]n → [0, 1] as
g i (x) := E[fci (x)].

(151)

c

Then this acceptance probability is
Pr[accept] =

X

[g i (x(1) )g i (x(2) ) . . . g i (x(k) )]

E
ρ

(152)

i∈[R] z,xi ←z

=

X

i∈[R]

i
k
E[(Tρ g (z)) ].

(153)

z

Notice that Ex [g i (x)] = 1/R, because
i
i
i+c
E[g (x)] = E [fc (x)] = E [f (x + (c, c, . . . , c))]
x

x,c

(c, x same joint distribution as i + c, x + c)

(154)

x,c

= E [f c (x)]

(155)

x,c

= E[E[f c (x)]] = E[1/R] = 1/R.
x c

(156)

x

Thus, if the function g i has small low-degree influences, then Lemma 3 (Main Lemma) applied to g i in
line (153) directly implies that this acceptance probability is 2O(k) /Rk−1 . We will now formally show
that the influences of the “expected folded function” g i are bounded by the influences of the original f i .
First, the Fourier coefficients of g i are
ĝ i (s) = E[fˆci (s)].
c

25

(157)

Thus the low-degree influences of g i are bounded as

X

Infj≤d [g i ] =

ĝ i (s)2

(158)

i
2
E[fˆc (s)]

(159)

i
2
E[fˆc (s) ]

(160)

fˆci (s)2 ]

(161)

s∈[R]n
s(j)6=1,|s|≤d

X

=

c

s∈[R]n
s(j)6=1,|s|≤d

≤

X

s∈[R]n
s(j)6=1,|s|≤d

X

= E[
c

c

s∈[R]n
s(j)6=1,|s|≤d

= E[Infj≤d [fci ]].

(162)

c

Finally, we must relate the influences of fci to the influences of f i . For a fixed c ∈ [R], we have
Infj≤d [fci ] = Infj [(fci )≤d ]
=
=
=

E [V

x∈[R]n

(163)

arxj ∈[R] [(fci )≤d ]]

(164)

i+c ≤d
E [V arxj ∈[R] [(f ) (x1 + c, x2 + c, . . . , xn + c)]]

(165)

i+c ≤d
E [V arxj ∈[R] [(f ) (x1 , x2 , . . . , xn )]]

(166)

x∈[R]n

x∈[R]n

= Infj [(f i+c )≤d ]

(167)

Infj≤d [f i+c ].

(168)

=

Therefore, if Infj≤d [f i ] ≤ δ for all coordinates j ∈ [n] and all projections i ∈ [R] (as we assume for
soundness), then from (162) and (168) we have
Infj≤d [g i ] ≤ E[Infj≤d [fci ]] = E[Infj≤d [f i+c ]] ≤ δ.
c

(169)

c

Thus the function g i has small low-degree influences as well.
So we can complete the proof, continuing from line (153) and applying our Main Lemma to g i :
Pr[accept] =

X

i∈[R]

(Lemma 3)

≤

X

i
k
E[(Tρ g (z)) ]

(170)

2O(k) /Rk

(171)

z

i∈[R]

= 2O(k) /Rk−1 .

26

(172)

