Authors Amey Bhangale, Prahladh Harsha, Girish Varma,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30
www.theoryofcomputing.org
A Characterization of Hard-to-Cover CSPs
Amey Bhangale∗ Prahladh Harsha† Girish Varma‡
Received October 13, 2016; Revised September 10, 2018; Published December 13, 2020
Abstract. We continue the study of the covering complexity of constraint satisfaction
problems (CSPs) initiated by Guruswami, Håstad and Sudan [SIAM J. Comp. 2002] and
Dinur and Kol [CCC’13]. The covering number of a CSP instance Φ is the smallest number
of assignments to the variables of Φ, such that each constraint of Φ is satisfied by at least
one of the assignments. We show the following results:
1. Assuming a covering variant of the Unique Games Conjecture, introduced by Dinur
and Kol, we show that for every non-odd predicate P over any constant-size alphabet
and every integer K, it is NP-hard to approximate the covering number within a factor
of K. This yields a complete characterization of CSPs over constant-size alphabets that
are hard to cover.
2. For a large class of predicates that are contained in the 2k-LIN predicate, we show that
it is quasi-NP-hard to distinguish between instances with covering number at most 2
and those with covering number at least Ω(log log n). This generalizes and improves
the 4-LIN covering hardness result of Dinur and Kol.
A preliminary version of this paper appeared in Proceedings of the 30th Computational Complexity Conference (CCC),
2015 [6].
∗ Research supported by the NSF grant CCF-1253886. Part of the work was done when the author was visiting TIFR.
† Supported in part by UGC-ISF Grant (6-2/2014(IC)) and the Swarnajayanti Fellowship Grant.
‡ Supported by Google India under the Google India Ph. D. Fellowship Award.
ACM Classification: F.2.2
AMS Classification: 68Q25
Key words and phrases: hardness of approximation, covering complexity, odd predicates
© 2020 Amey Bhangale, Prahladh Harsha and Girish Varma
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2020.v016a016
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
1 Introduction
One of the central (yet unresolved) questions in inapproximability is the problem of coloring a (hy-
per)graph with as few colors as possible. A (hyper)graph G = (V, E) is said to be k-colorable if there
exists a coloring c : V → [k] := {0, 1, 2, . . . , k − 1} of the vertices such that no (hyper)edge of G is
monochromatic. The chromatic number of a (hyper)graph, denoted by χ(G), is the smallest k such that G
is k-colorable. It is known that computing χ(G) to within a multiplicative factor of n1−ε on an n-vertex
graph G is NP-hard for every ε ∈ (0, 1) [9, 23]. However, the complexity of the following problem is not
yet completely understood: given a constant-colorable (hyper)graph, what is the minimum number of
colors required to color the vertices of the graph efficiently such that every edge is non-monochromatic?
The current best approximation algorithms for this problem require at least nΩ(1) colors [17] while the
hardness results are far from proving optimality of these approximation algorithms. (See Sec. 1.3 for a
discussion on recent work in this area.)
The notion of covering complexity was introduced by Guruswami, Håstad and Sudan [11] and more
formally by Dinur and Kol [8] to obtain a better understanding of the complexity of this problem. Let P
be a predicate and Φ an instance of a constraint satisfaction problem (CSP) over n variables, where each
constraint in Φ is a constraint of type P over the n variables and their negations. We will refer to such
CSPs as P-CSPs. The covering number of Φ, denoted by ν(Φ), is the smallest number of assignments
to the variables such that each constraint of Φ is satisfied by at least one of the assignments, in which
case we say that the set of assignments covers the instance Φ. If c assignments cover the instance Φ,
we say that Φ is c-coverable or equivalently that the set of assignments form a c-covering for Φ. The
covering number is a generalization of the notion of chromatic number (to be more precise, the logarithm
of the the chromatic number) to all predicates in the following sense. Let GΦ be the underlying constraint
(hyper)graph of the instance Φ whose vertices are the variables of the instance Φ and (hyper)edges are
in one-to-one correspondence with the constraints of Φ. Suppose P is the not-all-equal predicate NAE
and the instance Φ has no negations in any of its constraints, then the covering number ν(Φ) is exactly
dlog χ(GΦ )e where GΦ is the underlying constraint graph of the instance Φ.
Cover-P refers to the problem of finding the covering number of a given P-CSP instance. Finding the
exact covering number for most interesting predicates P is NP-hard. We therefore study the problem of
approximating the covering number. In particular, we would like to study the complexity of the following
problem, denoted by C OVERING-P-CSP(c, s), for some 1 ≤ c < s ∈ N: “given a c-coverable P-CSP
instance Φ, find an s-covering for Φ”. Similar problems have been studied for the Max-CSP setting: “for
0 < s < c ≤ 1, “given a c-satisfiable P-CSP instance Φ, find an s-satisfying assignment for Φ”. Max-CSPs
and Cover-CSPs, as observed by Dinur and Kol [8], are very different problems. For instance, if P is an
odd predicate, i.e, if for every assignment x, either x or its negation x + 1 satisfies P, then any P-CSP
instance Φ has a trivial 2-covering any assignment and its negation. Thus, 3-LIN and 3-CNF1 , being odd
predicates, are easy to cover though they are hard predicates in the Max-CSP setting. The main result of
Dinur and Kol is that the 4-LIN predicate which accepts odd parities, in contrast to the above, is hard to
cover: for every constant t ≥ 2, C OVERING-4-LIN-CSP(2,t) is NP-hard. In fact, their arguments show
that C OVERING-4-LIN-CSP(2, Ω(log log log n)) is quasi-NP-hard.
1 k-LIN : {0, 1}k → {0, 1} refers to the k-bit predicate defined by k-LIN(x , x , . . . , x ) := x ⊕ x ⊕ · · · ⊕ x while 3-CNF :
1 2 k 1 2 k
{0, 1}3 → {0, 1} refers to the 3-bit predicate defined by 3-CNF(x1 , x2 , x3 ) := x1 ∨ x2 ∨ x3
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 2
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
Having observed that CSPs based on odd predicates are easy to cover, Dinur and Kol proceeded to
ask the question “are all non-odd-predicate CSPs hard to cover?” In a partial answer to this question,
they showed that assuming a covering variant of the Unique Games Conjecture, C OVERING-UGC(c), if
a predicate P is not odd and there is a balanced pairwise independent distribution on its support, then
for all constants k, C OVERING-P-CSP(2c, k) is NP-hard. (Here, c is a fixed constant that depends on
the covering variant of the Unique Games Conjecture C OVERING-UGC(c).) See Sec. 2 for the exact
definition of the covering variant of the Unique Games Conjecture.
1.1 Our results
Our first result states that assuming the same covering variant of the Unique Games Conjecture,
C OVERING-UGC(c), of Dinur and Kol [8], one can in fact show the covering hardness of all non-
odd predicates P over any constant-size alphabet [q]. The notion of odd predicate can be extended to any
alphabet in the following natural way: a predicate P ⊆ [q]k is odd if for all assignments x ∈ [q]k , there
exists a ∈ [q] such that the assignment x + a satisfies P.
Theorem 1.1 (Covering hardness of non-odd predicates). Assuming C OVERING-UGC(c), for any
constant-size alphabet [q], any constant k ∈ N and any non-odd predicate P ⊆ [q]k , for all constants
t ∈ N, the C OVERING-P-CSP(2cq,t) problem is NP-hard.
Since odd predicates P ⊆ [q]k are trivially coverable with q assignments, the above theorem, gives a
full characterization of hard-to-cover predicates over any constant-size alphabet (modulo the covering
variant of the Unique Games Conjecture): a predicate is hard to cover iff it is not odd.
We then ask if we can prove similar covering hardness results under more standard complexity
assumptions (such as NP 6= P or the exponential-time hypothesis (ETH)). Though we are not able to
prove that every non-odd predicate is hard under these assumptions, we give sufficient conditions on
the predicate P for the corresponding approximate covering problem to be quasi-NP-hard. Recall that
2k-LIN ⊆ {0, 1}2k is the predicate corresponding to the set of odd parity strings in {0, 1}2k .
Theorem 1.2 (NP hardness of Covering). Let k ≥ 2. Let P ⊆ 2k-LIN be any 2k-bit predicate such there
exist distributions P0 , P1 supported on {0, 1}k with the following properties:
1. the marginals of P0 and P1 on all k coordinates are uniform,
2. every a ∈ supp(P0 ) has even parity and every b ∈ supp(P1 ) has odd parity and furthermore, both
a b, b a ∈ P, where a b denotes the 2k-bit string formed by the concatenation of strings a and b.
Then for all ε > 0, r 1, there is a reduction from 3SAT to C OVERING-P-CSP mapping a 3SAT
O(r) O(r)
instance Ψ on n variables to a C OVERING-P-CSP instance Φ of size nO(r) 22 in time nO(r) 22 such
that
• YES Case: If the 3SAT formula Ψ is satisfiable then there are 2 assignments each satisfying 1 − ε
of the constraints of Φ, that together cover the instance Φ.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 3
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
• NO Case: if the 3SAT formula Ψ is not satisfiable, then the resulting instance Φ is not Ωk (r) −
Ok (log(1/ε)) coverable, even when considered as an instance of the (potentially larger) predicate
2k-LIN.
In particular, unless NP ⊆ DTIME(2poly log n ), C OVERING-P-CSP(2, Ω(log log n)) does not have a
polynomial-time algorithm.
If we assume P 6= NP then C OVERING-P-CSP(2,C) does not have a polynomial-time algorithm for
any constant C > 2.
The furthermore clause in the soundness guarantee is in fact a strengthening for the following reason:
if two predicates P, Q satisfy P ⊆ Q and Φ is a c-coverable P-CSP instance, then the Q-CSP instance
ΦP→Q obtained by taking the constraint graph of Φ and replacing each P constraint with the weaker Q
constraint, is also c-coverable.
The following is a simple corollary of the above theorem.
Corollary 1.3. Let k ≥ 2 be even, x, y ∈ {0, 1}k be distinct strings having even and odd parity, respectively,
and x, y denote the complements of x and y, respectively. For any predicate P satisfying
2k-LIN ⊇ P ⊇ {x y, x y, x y, x y, y x, y x, y x, y x},
unless NP ⊆ DTIME(2poly log n ), the problem C OVERING-P-CSP(2, Ω(log log n)) is not solvable in poly-
nomial time.
This corollary implies the covering hardness of 4-LIN predicate proved by Dinur and Kol [8] by
setting x := 00 and y := 01. With respect to the covering hardness of 4-LIN, we note that we can
considerably simplify the proof of Dinur and Kol and in fact obtain a even stronger soundness guarantee
(see Theorem below). The stronger soundness guarantee in the theorem below states that there are no
large (≥ 1/ poly log n fractional-size) independent sets in the constraint graph and hence, even the 4-NAE-
CSP instance2 with the same constraint graph as the given instance is not coverable using Ω(log log n)
assignments. Both the Dinur–Kol result and the above corollary only guarantee (in the soundness case)
that the 4-LIN-CSP instance is not coverable.
Theorem 1.4 (Hardness of Covering 4-LIN). Assuming that NP 6⊆ DTIME(2poly log n ), for all ε ∈ (0, 1),
there does not exist a polynomial-time algorithm that can distinguish between 4-LIN-CSP instances of
the following two types:
• YES Case : There are 2 assignments such that each of them covers 1 − ε fraction of the constraints,
and they together cover the entire instance.
• NO Case : The largest independent set in the constraint graph of the instance is of fractional size
at most 1/ poly log n.
2 The k-NAE predicate over k bits is given by k-NAE = {0, 1}k \ {0, 1}.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 4
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
1.2 Techniques
As one would expect, our proofs are very much inspired from the corresponding proofs in Dinur and
Kol [8]. One of the main complications in the proof of Dinur and Kol [8] (as also in the earlier work of
Guruswami, Håstad and Sudan [11]) was the one of handling several assignments simultaneously while
proving the soundness analysis. For this purpose, both these works considered the rejection probability
that all the assignments violated the constraint. This resulted in a very tedious expression for the rejection
probability, which made the rest of the proof fairly involved. Holmerin [14] observed that this can be
considerably simplified if one instead proved a stronger soundness guarantee that the largest independent
set in the constraint graph is small (this might not always be doable, but in the cases when it is, it simplifies
the analysis). We list below the further improvements in the proof that yield our Theorems 1.1, 1.2
and 1.4.
Covering-UG hardness for non-odd predicates (Theorem 1.1). Having observed that it suffices to
prove an independent set analysis, we observed that only very mild conditions on the predicate are
required to prove covering hardness. In particular, while Dinur and Kol used the Austrin–Mossel test [3]
which required pairwise independence, we are able to import the long-code test of Bansal and Khot [4]
which requires only 1-wise independence. We remark that the Bansal–Khot Test was designed for a
specific predicate (hardness of finding independent sets in almost k-partite k-uniform hypergraphs) and
had imperfect completeness. Our improvement comes from observing that their test requires only 1-wise
independence and furthermore that their completeness condition, though imperfect, can be adapted
to give a 2-cover composed of 2 nearly satisfying assignments using the duplicate label technique of
Dinur–Kol. This enlarges the class of non-odd predicates for which one can prove covering hardness
(see Theorem 3.1). We then perform a sequence of reductions from this class of CSP instances to CSP
instances over all non-odd predicates to obtain the final result. Interestingly, one of the open problems
mentioned in the work of Dinur and Kol [8] was to devise “direct” reductions between covering problems.
The reductions we employ, strictly speaking, are not “direct” reductions between covering problems,
since they rely on a stronger soundness guarantee for the source instance (namely, large covering number
even for the NAE instance on the same constraint graph), which we are able to prove in Theorem 3.1.
We give an overview of the dictatorship test gadget which when composed with a covering-UG
instance, gives the required covering hardness result. Let P ⊆ [q]k be a predicate such that there exists
a ∈ NAE and
NAE ⊃ P ⊇ {a + b̄ | b ∈ [q]},
i. e., P accepts all shifts of a particular assignment a ∈ [q]k where a ∈ NAE. We are given a function f :
[q]2L → [q] and are interested in a k-query test, querying at (x1 , x2 , . . . , xk ) according to some distribution
D, which has the following three properties:
1. The accepting criteria of the test is ( f (x1 ), f (x2 ), . . . , f (xk )) ∈ P
2. For every i ∈ [L], the test should accept with probability 1 if f is either the i-th dictator or the
(i + L)-th dictator.
3. If f is far from any dictator then the test, even with the predicate P replaced by NAE, should reject
with significant probability.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 5
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
We can think of the queries as a k × 2L matrix X where the rows represent x1 , x2 , . . . , xk . Here is a
distribution D for which the test has all the above three properties: It will be a L-wise product distribution
µ ⊗L , where µ is a distribution on ([q]k )2 sampled uniformly from the set S,
n o
S := (y, y0 ) ∈ [q]k × [q]k | y ∈ {a + b̄ | b ∈ [q]} ∨ y0 ∈ {a + b̄ | b ∈ [q]} .
For each i ∈ [L] we sample the i-th and (i + L)-th columns of X independently from µ. This completes
the description of the distribution D. It is clear from the construction that the test with accepting criteria
(1) satisfies (2) as either the i-th column or the (i + L)-th column contains an accepting assignment. The
argument that (3) also holds for this test crucially depends on the properties of the distribution µ – that
each query xi is distributed uniformly in {0, 1}2L and the distribution µ is connected (see Definition 2.7),
when viewed as a probability space (([q]2 )k , µ). Using both these properties of the distribution µ, we
can then apply the invariance principle to argue that the constrained (hyper)graph formed by the test
distribution has a small independent set, which in turns imply (3).
Quasi-NP hardness result (Theorem 1.2). In this setting, we unfortunately are not able to use the
simplification arising from using the independent set analysis and have to deal with the issue of several
assignments. One of the steps in the 4-LIN proof of Dinur and Kol (as in several others results in this
area) involves showing that a expression of the form E(X,Y ) [F(X)F(Y )] is not too negative where (X,Y )
is not necessarily a product distribution but the marginals on the X and Y parts are identical. Observe
that if (X,Y ) was a product distribution, then the above expressions reduces to (EX [F(X)])2 , a positive
quantity. Thus, the steps in the proof involve constructing a tailor-made distribution (X,Y ) such that the
error in going from the correlated probability space (X,Y ) to the product distribution (X ⊗Y ) is not too
much. More precisely, the quantity
E [F(X)F(Y )] − E [F(X)] E [F(Y )] ,
(X,Y ) X Y
is small. Dinur and Kol used a distribution tailor-made for the 4-LIN predicate and used an invariance
principle for correlated spaces to bound the error while transforming it to a product distribution. Our
improvement comes from observing that one could use an alternate invariance principle (see Theorem 2.9)
that works with milder restrictions and hence works for a wider class of predicates. This invariance prin-
ciple for correlated spaces (Theorem 2.9) is an adaptation of invariance principles proved by Wenner [22]
and Guruswami and Lee [12] in similar contexts. The rest of the proof is similar to the 4-LIN covering
hardness proof of Dinur and Kol.
Covering hardness of 4-LIN (Theorem 1.4). The simplified proof of the covering hardness of 4-LIN
follows directly from the above observation of using an independent set analysis instead of working with
several assignments. In fact, this alternate proof eliminates the need for using results about correlated
spaces [18], which was crucial in the Dinur–Kol setting. We further note that the quantitative improvement
in the covering hardness (Ω(log log n) over Ω(log log log n)) comes from using a L ABEL -C OVER instance
with a better smoothness property (see Theorem 2.5).
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 6
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
1.3 Recent work on approximate coloring
Besides the work on covering complexity, the works most related to our paper are the series of works
that study the approximate coloring complexity question, stated in the beginning of the introduction.
Saket [20] showed that unless NP ⊆ DTIME(2poly log n ), it is not possible to color a 2-colorable 4-uniform
hypergraph with poly log n colors. We remark that recently, with the discovery of the short code [5], there
has been a sequence of works [7, 10, 16, 21, 15] which have considerably improved the status of the
approximate coloring question. In particular, we know that it is quasi-NP-hard to color a 2-colorable
c
8-uniform hypergraph with 2(log n) colors for some constant c ∈ (0, 1). Stated in terms of covering
number, this result states that it is quasi-NP-hard to cover a 1-coverable 8-NAE-CSP instance with
(log n)c assignments. It is to be noted that these results pertain to the covering complexity of specific
predicates (such as NAE) whereas our results are concerned with classifying which predicates are hard
to cover. It would be interesting if Theorems 1.2 and 1.4 can be improved to obtain similar hardness
results (i. e., poly log n as opposed to poly log log n). The main bottleneck here seems to be reducing the
uniformity parameter (namely, from 8).
Organization
The rest of the paper is organized as follows. We start with some preliminaries of L ABEL -C OVER,
covering CSPs and Fourier analysis in Sec. 2. Theorems 1.1, 1.2 and 1.4 are proved in Sections 3, 4 and 5,
respectively.
2 Preliminaries
2.1 Covering CSPs
We will denote the set {0, 1, · · · q − 1} by [q]. For a ∈ [q], ā ∈ [q]k is the element with a in all the k
coordinates (where k and q will be implicit from the context).
Definition 2.1 (P-CSP). For a predicate P ⊆ [q]k , an instance of P-CSP is given by a (hyper)graph
G = (V, E), referred to as the constraint graph, and a literals function L : E → [q]k , where V is a set of
variables and E ⊆ V k is a set of constraints. An assignment f : V → [q] is said to cover a constraint
e = (v1 , · · · , vk ) ∈ E, if ( f (v1 ), · · · , f (vk )) + L(e) ∈ P, where addition is coordinate-wise modulo q. A
set of assignments F = { f1 , · · · , fc } is said to cover (G, L), if for every e ∈ E, there is some fi ∈ F that
covers e and F is said to be a c-covering for G. G is said to be c-coverable if there is a c-covering for G.
If L is not specified then it is the constant function which maps E to 0̄.
Definition 2.2 (C OVERING-P-CSP(c, s)). For P ⊆ [q]k and c, s ∈ N, the C OVERING-P-CSP(c, s) problem
is, given a c-coverable instance (G = (V, E), L) of P-CSP, find an s-covering.
Definition 2.3 (Odd). A predicate P ⊆ [q]k is odd if ∀x ∈ [q]k , ∃a ∈ [q], x + ā ∈ P, where addition is
coordinate-wise modulo q.
For odd predicates the covering problem is trivially solvable, since any CSP instance on such a
predicate is q-coverable by the q translates of any assignment, i. e., {x + ā | a ∈ [q]} is a q-covering for
any assignment x ∈ [q]k .
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 7
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
2.2 Label Cover
Definition 2.4 (L ABEL -C OVER). An instance G = (U,V, E, L, R, {πe }e∈E ) of the L ABEL -C OVER con-
straint satisfaction problem consists of a bi-regular bipartite graph (U,V, E), two sets of alphabets L and
R and a projection map πe : R → L for every edge e ∈ E. Given a labeling ` : U → L, ` : V → R, an edge
e = (u, v) is said to be satisfied by ` if πe (`(v)) = `(u).
G is said to be at most δ -satisfiable if every labeling satisfies at most a δ fraction of the edges. G
is said to be c-coverable if there exist c labelings such that for every vertex u ∈ U, one of the labelings
satisfies all the edges incident on u.
An instance of U NIQUE -G AMES is a label cover instance where L = R and the constraints π are
permutations.
The hardness of L ABEL -C OVER stated below follows from the PCP Theorem [2, 1], Raz’s Parallel
Repetition Theorem [19] and a structural property proved by Håstad [13, Lemma 6.9].
Theorem 2.5 (Hardness of L ABEL -C OVER). For every r ∈ N, there is a deterministic nO(r) -time reduction
from a 3-SAT instance of size n to an instance G = (U,V, E, [L], [R], {πe }e∈E ) of L ABEL -C OVER with the
following properties:
1. |U|, |V | ≤ nO(r) ; L, R ≤ 2O(r) ; G is bi-regular with degrees bounded by 2O(r) .
2. There exists a constant c0 ∈ (0, 1/3) such that for any v ∈ V and α ⊆ [R], for a random neighbor u,
E |πuv (α)|−1 ≤ |α|−2c0 ,
u
where πuv (α) := {i ∈ [L] | ∃ j ∈ α s.t. πuv ( j) = i}. This implies that
1
∀v, α, Pru [|πuv (α)| < |α|c0 ] ≤ .
|α|c0
3. There is a constant d0 ∈ (0, 1) such that,
• YES Case : If the 3-SAT instance is satisfiable, then G is 1-coverable.
• NO Case : If the 3-SAT instance is unsatisfiable, then G is at most 2−d0 r -satisfiable.
Our characterization of hardness of covering CSPs is based on the following conjecture due to Dinur
and Kol [8].
Conjecture 2.6 (C OVERING-UGC(c)). There exists c ∈ N such that for every sufficiently small δ > 0
there exists L ∈ N such that the following holds. Given an instance G = (U,V, E, [L], [L], {πe }e∈E ) of
U NIQUE -G AMES it is NP-hard to distinguish between the following two cases:
• YES case: There exist c assignments such that for every vertex u ∈ U, at least one of the assignments
satisfies all the edges touching u.
• NO case: Every assignment satisfies at most δ fraction of the edge constraints.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 8
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
2.3 Analysis of Boolean functions over probability spaces
For a function f : {0, 1}L → R, the Fourier decomposition of f is given by
L
f (x) = ∑ fb(α)χα (x) where χα (x) := (−1)∑i=1 αi ·xi and fb(α) := E f (x)χα (x).
x∈{0,1}L
α∈{0,1}L
We will use α, also to denote the subset of [L] for which it is the characteristic vector. The Efron–Stein
decomposition is a generalization of the Fourier decomposition to product distributions of arbitrary
probability spaces. Let (Ω, µ) be a probability space and (ΩL , µ ⊗L ) be the corresponding product space.
For a function f : ΩL → R, the Efron–Stein decomposition of f with respect to the product space is given
by
f (x1 , · · · , xL ) = ∑ fβ (x),
β ⊆[L]
0
where fβ depends only on xi for i ∈ β and for all β 0 6⊇ β , a ∈ Ωβ , Ex∈µ ⊗R fβ (x) | xβ 0 = a = 0. We will
be dealing with functions of the form f : {0, 1}dL → R for d ∈ N and d-to-1 functions π : [dL] → [L]. We
will also think of such functions as f : ∏i∈L Ωi → R where Ωi = {0, 1}d consists of the d coordinates j
such that π( j) = i. An Efron–Stein decomposition of f : ∏i∈L Ωi → R over the uniform distribution over
{0, 1}dL , can be obtained from the Fourier decomposition as
fβ (x) = ∑ fb(α)χα . (2.1)
α⊆[dL]:π(α)=β
Let k f k2 := Ex∈µ ⊗L [ f (x)2 ]1/2 and k f k∞ := maxx∈Ω⊗L | f (x)| . For i ∈ [L], the influence of the i-th coordi-
nate on f is defined as follows.
Inf i [ f ] := E Varxi [ f (x1 , · · · , xL )] = ∑ k fβ k22 .
x1 ,··· ,xi−1 ,xi+1 ,··· ,xL
β :i∈β
For an integer d, the degree d influence is defined as
Inf ≤d
i [ f ] := ∑ k fβ k22 .
β :i∈β ,|β |≤d
It is easy to see that for Boolean functions, the sum of all the degree d influences is at most d.
Definition 2.7. Let (Ωk , µ) be a probability space. Let S = {x ∈ Ωk | µ(x) > 0}. We say that S ⊆ Ωk is
connected if for every x, y ∈ S, there is a sequence of strings starting with x and ending with y such that
every element in the sequence is in S and every two adjacent elements differ in exactly one coordinate.
Let µ ⊗n denote the n-wise product distribution of µ.
Theorem 2.8 ([18, Proposition 6.4]). Let (Ωk , µ) be a probability space such that the support of the
distribution supp(µ) ⊆ Ωk is connected and the minimum probability of every atom in supp(µ) is at
least α for some α ∈ (0, 1/2]. Furthermore, assume that the marginal of µ on each of the k coordinates
is uniform in Ω. Then there exist continuous functions Γ : (0, 1) → (0, 1) and Γ : (0, 1) → (0, 1) such
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 9
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
that the following holds: For every ε > 0, there exists τ > 0 and an integer d such that if a function
f : ΩL → [0, 1] satisfies
∀i ∈ [L], Inf ≤d
i (f) ≤ τ
then
" #
k
Γ E [ f (x1 )] − ε ≤ E ∏ f (x j ) ≤ Γ (x ,...,xE)∼µ [ f (x1 )] + ε.
(x1 ,...,xk )∼µ ⊗L (x1 ,...,xk )∼µ ⊗L j=1 1 k
⊗L
1 1
C log( /α) log( /ε)
There exists an absolute constant C such that one can take τ = ε εα2
and d = log(1/τ ) log(1/α ).
The following invariance principle for correlated spaces proved in Section 6 is an adaptation of similar
invariance principles (c.f., [22, Theorem 3.12], [12, Lemma B.3]) to our setting.
Theorem 2.9 (Invariance Principle for correlated spaces). Let (Ωk1 × Ωk2 , µ) be a correlated probability
space such that the marginal of µ on any pair of coordinates one each from Ω1 and Ω2 is a product
distribution. Let µ1 , µ2 be the marginals of µ on Ωk1 and Ωk2 , respectively. Let X,Y be two random k × L
dimensional matrices chosen as follows. Independently for every i ∈ [L], the pair of columns (xi , yi ) ∈
Ωk1 × Ωk2 is chosen from µ. Let xi , yi denote the i-th rows of X and Y , respectively. If F : ΩL1 → [−1, +1]
and G : ΩL2 → [−1, +1] are functions such that
s s s
τ := ∑ Inf i [F] · Inf i [G] and Γ := max ∑ i Inf [F] , ∑ i ,
Inf [G]
i∈[L]
i∈[L] i∈[L]
then " # " # " #
E ∏ F(xi ) · G(yi ) − X∈µE ∏ F(xi ) · Y ∈µE ∏ G(yi ) ≤ 2O(k) Γτ . (2.2)
(X,Y )∈µ ⊗L i∈[k]
⊗L
1 i∈[k]
⊗L
2 i∈[k]
3 Covering-UG Hardness of Covering CSPs
In this section, we prove the following theorem, which in turn implies Theorem 1.1 (see below for proof).
Theorem 3.1. Let [q] be any constant-size alphabet and k ≥ 2. Recall that NAE := [q]k \ {b̄ | b ∈ [q]}.
Let P ⊆ [q]k be a predicate such that there exists a ∈ NAE and NAE ⊃ P ⊇ {a + b̄ | b ∈ [q]}. Assuming
C OVERING-UGC(c), for every sufficiently small constant δ > 0 it is NP-hard to distinguish between
P-CSP instances G = (V, E) of the following two cases:
• YES Case : G is 2c-coverable.
• NO Case : G does not have an independent set of fractional size δ .
Proof of Theorem 1.1. Let Q be an arbitrary non-odd predicate i.e, Q ⊆ [q]k \ {h + b̄ | b ∈ [q]} for some
h ∈ [q]k . Consider the predicate Q0 ⊆ [q]k defined as Q0 := Q − h := {g − h | g ∈ Q}, where the operation
‘−’ refers to coordinate-wise substraction performed (mod q). Observe that Q0 ⊆ NAE. Given any
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 10
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
Q0 -CSP instance Φ with literals function L(e) = 0, consider the Q-CSP instance ΦQ0 →Q with literals
function M given by M(e) := h, ∀e. It has the same constraint graph as Φ. Clearly, Φ is c-coverable
iff ΦQ0 →Q is c-coverable. Thus, it suffices to prove the result for any predicate Q0 ⊆ NAE with literals
function L(e) = 03 . We will consider two cases, both of which will follow from Theorem 3.1.
Suppose the predicate Q0 satisfies Q0 ⊇ {a + b̄ | b ∈ [q]} for some a ∈ [q]k . Then this predicate Q0
satisfies the hypothesis of Theorem 3.1 and the theorem follows if we show that the soundness guarantee
of Theorem 3.1 implies that in Theorem 1.1. Any instance in the NO case of Theorem 3.1, is not
t := logq (1/δ )-coverable even on the NAE-CSP instance with the same constraint graph. This is because
any t-covering for the NAE-CSP instance gives a coloring of the constraint graph using qt colors, by
choosing the color of every variable to be a string of length t and having the corresponding assignments
in each position in [t]. Hence the Q0 -CSP instance is also not t-coverable.
Suppose Q0 6⊇ {a + b̄ | b ∈ [q]} for all a ∈ [q]k . Then consider the predicate P = {a + b̄ | a ∈ Q0 , b ∈
[q]} ⊆ NAE. Notice that P satisfies the conditions of Theorem 3.1 and if the P-CSP instance is t-coverable
then the Q0 -CSP instance is qt-coverable. Hence a YES instance of Theorem 3.1 maps to a 2cq-coverable
Q-CSP instance and NO instance maps to an instance with covering number at least logq (1/δ ), where the
latter follows from the fact that the covering number of the instance as a Q0 -CSP is at least the covering
number of it as a P-CSP.
We now prove Theorem 3.1 by giving a reduction from an instance G = (U,V, E, [L], [L], {πe }e∈E )
of U NIQUE -G AMES as in Definition 2.4, to an instance G = (V, E) of a P-CSP for any predicate P
that satisfies the conditions mentioned. As stated in the introduction, we adapt the long-code test of
Bansal and Khot [4] for proving the hardness of finding independent sets in almost k-partite k-uniform
hypergraphs to our setting. The set of variables V is V × [q]2L . Any assignment to V is given by a set of
functions fv : [q]2L → [q], for each v ∈ V . The set of constraints E is given by the following test which
checks whether fv ’s are long codes of a good labeling to V . There is a constraint corresponding to all the
variables that are queried together by the test.
Long Code Test T1
1. Choose u ∈ U uniformly and k neighbors w1 , . . . , wk ∈ V of u uniformly and independently at
random.
2. Choose a random matrix X of dimension k × 2L as follows. Let X i denote the i-th column of X.
Independently for each i ∈ [L], choose (X i , X i+L ) uniformly at random from the set
n o
S := (y, y0 ) ∈ [q]k × [q]k | y ∈ {a + b̄ | b ∈ [q]} ∨ y0 ∈ {a + b̄ | b ∈ [q]} . (3.1)
3. Let x1 , · · · , xk be the rows of matrix X. Accept iff
( fw1 (x1 ◦ πuw1 ), fw2 (x2 ◦ πuw2 ), · · · , fwk (xk ◦ πuwk )) ∈ P,
where x ◦ π is the string defined as (x ◦ π)(i) := xπ(i) for i ∈ [L] and (x ◦ π)(i) := xπ(i−L)+L otherwise.
3 This observation [8] that the cover-Q problem for any non-odd predicate Q is equivalent to the cover-Q0 problem where
Q0 ⊆ NAE shows the centrality of the NAE predicate in understanding the covering complexity of any non-odd predicate.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 11
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
Before plunging into the formal analysis of the reduction, let us see the intuition behind the test. The
test is designed so that if the functions fw1 , fw2 , . . . , fwk are dictator functions satisfying the UG-constraints
associated with the common neighbor u or their L shifts, then the test passes. This is obvious as the bit
pattern from the locations queried is either y or y0 , one of which belongs to the predicate P. This gives a
2-covering of the instance: one corresponds to the actual dictator functions satisfying the UG-constraints
and another consists of L shifts of those dictator functions. Another property of the set S that is used in
the test is that it defines a probability space that is connected. This will be used in the soundness analysis
of the test. We now prove the completeness and the soundness of the reduction.
Lemma 3.2 (Completeness). If the U NIQUE -G AMES instance G is c-coverable then the P-CSP instance
G is 2c-coverable.
Proof. Let `1 , . . . , `c : U ∪V → [L] be a c-covering for G as described in Definition 2.4. We will show that
the 2c assignments given by fvi (x) := x`i (v) , giv (x) := x`i (v)+L , i = 1, . . . , c form a 2c-covering of G. Consider
any u ∈ U and let `i be the labeling that covers all the edges incident on u. For any (u, w j ) j∈{1,··· ,k} ∈ E
and X chosen by the long code test T1 , the vector ( fwi 1 (x1 ◦ πuw1 ), · · · , fwi k (xk ◦ πuwk )) gives the `i (u)-th
column of X. Similarly the above expression corresponding to gi gives the (`i (u) + L)-th column of the
matrix X. Since, for all i ∈ [L], either i-th column or (i + L)-th column of X contains element from {a + b̄ |
b ∈ [q]} ⊆ P, either ( fwi 1 (x1 ◦ πuw1 ), · · · , fwi k (xk ◦ πuwk )) ∈ P or (giw1 (x1 ◦ πuw1 ), · · · , giwk (xk ◦ πuwk )) ∈ P.
Hence the set of 2c assignments { fvi , giv }i∈{1,··· ,c} covers all constraints in G.
To prove soundness, we show that the set S, as defined in Equation (3.1), is connected, so that
Theorem 2.8 is applicable. For this, we view S ⊆ [q]k × [q]k as a subset of ([q]2 )k as follows: the element
(y, y0 ) ∈ S is mapped to the element ((y1 , y01 ), · · · , (yk , y0k )) ∈ ([q]2 )k .
Claim 3.3. Let Ω = [q]2 . The set S ⊂ Ωk is connected.
Proof. Consider any x := (x1 , x2 ), y := (y1 , y2 ) ∈ S ⊂ [q]k × [q]k . Suppose both x1 , y1 ∈ {a + b̄ | b ∈ [q]},
then it is easy to come up with a sequence of strings belonging to S, starting with x and ending with
y such that consecutive strings differ in at most 1 coordinate,. Now suppose x1 , y2 ∈ {a + b̄ | b ∈ [q]}.
First we come up with a sequence from x to z := (z1 , z2 ) such that z1 := x1 and z2 = y2 , and then another
sequence for z to y.
Lemma 3.4 (Soundness). For every constant δ > 0, there exists a constant s such that, if G is at most
s-satisfiable then G does not have an independent set of size δ .
Proof. Let I ⊆ V be an independent set of fractional size δ in the constraint graph. For every variable
v ∈ V , let fv : [q]2L → {0, 1} be the indicator function of the independent set restricted to the vertices
that correspond to v. For a vertex u ∈ U, let N(u) ⊆ V be the set of neighbors of u and define fu (x) :=
Ew∈N(u) [ fw (x ◦ πuw )]. Since I is an independent set, we have
" # " #
k k
0= E E
u,wi ,...,wk X∼T1
∏ fw (xi ◦ πuw ) = Eu X∼T
i i E ∏ fu (xi ) .
1
(3.2)
i=1 i=1
Since the bipartite graph (U,V, E) is left regular and |I| ≥ δ |V |, we have Eu,x [ fu (x)] ≥ δ . By an averaging
argument, for at least δ/2 fraction of the vertices u ∈ U, Ex [ fu (x)] ≥ δ/2. Call a vertex u ∈ U good if it
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 12
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
satisfies this property. A string x ∈ [q]2L can be thought as an element from ([q]2 )L by grouping the pair
of coordinates xi , xi+L . Let x ∈ ([q]2 )L denotes this grouping of x, i. e., j-th coordinate of x is (x j , x j+L ) is
distributed u.a.r. in [q]2 . With this grouping, the function fu can be viewed as fu : ([q]2 )L → {0, 1}. From
Equation (3.2), we have that for any u ∈ U,
" #
k
E ∏ fu (xi ) = 0.
X∼T1 i=1
By Claim 3.3, for all j ∈ [L] the tuple ((x1 ) j , . . . , (xk ) j ) (corresponding to columns (X j ,X j+L ) of X) is
sampled from a distribution whose support is a connected set. Hence for a good vertex u ∈ U, we can
apply Theorem 2.8 with ε = Γ(δ /2)/2 to get that there exists j ∈ [L], d ∈ N, τ > 0 such that Inf ≤d j ( f u ) > τ.
We will use this fact to give a randomized labeling for G. Labels for vertices w ∈ V, u ∈ U will be chosen
uniformly and independently from the sets
n τo n o
Lab(w) := i ∈ [L] | Inf ≤d
i ( f w ) ≥ , Lab(u) := i ∈ [L] | Inf ≤d
i ( f u ) ≥ τ .
2
By the above argument (using Theorem 2.8), we have that for a good vertex u, Lab(u) 6= 0.
/ Furthermore,
since the sum of degree d influences is at most d, the above sets have size at most 2d/τ. Now, for any
j ∈ Lab(u), we have
h i 2
τ < Inf ≤d
j [ fu ] = ∑ k fu,S k2 = ∑ E fw,πuw
−1
(S) (By Definition.)
S: j∈S,|S|≤d S: j∈S,|S|≤d w∈N(u)
2
≤ ∑ E fw,πuw
−1
(S) = E Inf ≤d [ f ]. (By Convexity of square.)
π −1 ( j) w
uw
S: j∈S,|S|≤d w∈N(u) w∈N(u)
Hence, by another averaging argument, there exists at least τ/2 fraction of neighbors w of u such that
Inf ≤d
−1
πuw
( f ) ≥ τ/2 and hence πuw
( j) w
−1 ( j) ∈ Lab(w). Therefore, for a good vertex u ∈ U, at least τ/2 · τ/2d
fraction of edges incident on u are satisfied in expectation. Also, at least δ/2 fraction of vertices in U are
good, it follows that the expected fraction of edges that are satisfied by this random labeling is at least
δ/2 · τ/2 · τ/2d . Choosing s < δ τ 2/8d completes the proof.
4 NP Hardness of Covering CSPs
In this section, we prove Theorem 1.2. We give a reduction from an instance of a L ABEL -C OVER,
G = (U,V, E, [L], [R], {πe }e∈E ) as in Definition 2.4, to a P-CSP instance G = (V, E) for any predicate P
that satisfies the conditions mentioned in Theorem 1.2. The reduction and proof is similar to that of Dinur
and Kol [8]. The main difference is that they used a test and invariance principle very specific to the
4-LIN predicate, while we show that a similar analysis can be performed under milder conditions on the
test distribution.
We assume that R = dL and ∀i ∈ [L], e ∈ E, |πe−1 (i)| = d. This is done just for simplifying the notation
and the proof does not depend upon it. The set of variables V is V × {0, 1}2R . Any assignment to V is
given by a set of functions fv : {0, 1}2R → {0, 1}, for each v ∈ V . The set of constraints E is given by the
following test, which checks whether fv ’s are long codes of a good labeling to V .
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 13
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
Long Code test T2
1. Choose u ∈ U uniformly and v, w ∈ V neighbors of u uniformly and independently at random. For
−1 (i), B0 (i) := R + π −1 (i) and similarly for w.
i ∈ [L], define the sets Buv (i) := πuv uv uv
2. Choose matrices X,Y of dimension k × 2dL as follows. For S ⊆ [2dL], we denote by X|S the
submatrix of X restricted to the columns S. Independently for each i ∈ [L], choose c1 ∈ {0, 1}
uniformly and
(a) if c1 = 0, choose X|Buv (i)∪B0uv (i) ,Y |Buw (i)∪B0uw (i) from P⊗2d ⊗ P⊗2d
0 1 ,
(b) if c1 = 1, choose X|Buv (i)∪B0uv (i) ,Y |Buw (i)∪B0uw (i) from P1 ⊗ P⊗2d
⊗2d
0 .
3. Perturb X,Y as follows. Independently for each i ∈ [L], choose c2 ∈ {∗, 0, 1} as follows:
Pr[c2 = ∗] = 1 − 2ε, and Pr[c2 = 1] = Pr[c2 = 0] = ε.
Perturb the i-th matrix block X|Buv (i)∪B0uv (i) ,Y |Buw (i)∪B0uw (i) as follows:
(a) if c2 = ∗, leave the matrix block X|Buv (i)∪B0uv (i) ,Y |Buw (i)∪B0uw (i) unperturbed,
(b) if c2 = 0, choose X|B0uv (i) ,Y |B0uw (i) uniformly from {0, 1}k×d × {0, 1}k×d ,
(c) if c2 = 1, choose X|Buv (i) ,Y |Buw (i) uniformly from {0, 1}k×d × {0, 1}k×d .
4. Let x1 , · · · , xk and y1 , · · · , yk be t he rows of the matrices X and Y , respectively. Accept if
( fv (x1 ), · · · , fv (xk ), fw (y1 ), · · · , fw (yk )) ∈ P.
Lemma 4.1 (Completeness). If G is an YES instance of L ABEL -C OVER, then there exists f , g such that
each of them covers 1 − ε fraction of E and they together cover all of E.
Proof. Let ` : U ∪ V → [L] ∪ [R] be a labeling to G that satisfies all the constraints. Consider the
assignments fv (x) := x`(v) and gv (x) := xR+`(v) for each v ∈ V . First consider the assignment f . For
any (u, v), (u, w) ∈ E and x1 , · · · , xk , y1 , · · · , yk chosen by the long code test T2 , ( fv (x1 ), · · · , fv (xk )),
( fw (y1 ), · · · , fw (yk )) gives the `(v)-th and `(w)-th column of the matrices X and Y , respectively. Since
πuv (`(v)) = πuw (`(w)), they are jointly distributed either according to P0 ⊗ P1 or P1 ⊗ P0 after Step 2.
The probability that these rows are perturbed in Step 3c is at most ε. Hence with probability 1 − ε over
the test distribution, f is accepted. A similar argument shows that the test accepts g with probability
1 − ε. Note that in Step 3, the columns given by f , g, are never re-sampled uniformly together. Hence
they together cover G.
Now we will show that if G is a NO instance of L ABEL -C OVER then no t assignments can cover the
2k-LIN-CSP with constraint hypergraph G. For the rest of the analysis, we will use +1, −1 instead of the
symbols 0, 1. Suppose for contradiction, there exist t assignments f1 , · · · , ft : {±1}2R → {±1} that form
a t-cover to G. The probability that all the t assignments are rejected in Step 4 is
" !# " #
t k k
1 1 1
E E ∏ ∏ fi,v (x j ) fi,w (y j ) + 1 = t+ t ∑ u,v,w E E ∏ fS,v (x j ) fS,w (y j ) . (4.1)
u,v,w T2 T2
i=1 2 j=1 2 2 0⊂S⊆{1,···
/ ,t} j=1
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 14
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
where fS,v (x) := ∏i∈S fi,v (x). Since the t assignments form a t-cover, the LHS in Equation (4.1) is 0 and
hence, there exists an S 6= 0/ such that
" #
k
E E
u,v,w T2
∏ fS,v (x j ) fS,w (y j ) ≤ −1/(2t − 1). (4.2)
j=1
The following lemma shows that this is not possible if t is not too large, thus proving that there does not a
exist t-cover.
Lemma 4.2 (Soundness). Let c0 ∈ (0, 1) be the constant from Theorem 2.5 and S ⊆ {1, · · · ,t}, |S| > 0. If
G is at most s-satisfiable then
" #
k (1−3c0 )/8
c0 /8 O(k) s
E E f (x ) f
∏ S,v i S,w i (y ) ≥ −O(ks ) − 2 .
u,v,w X,Y ∈T2
i=1 ε 3/2c0
Proof. Notice that for a fixed u, the distribution of X and Y have identical marginals. Hence the value of
the above expectation, if calculated according to a distribution that is the direct product of the marginals,
is positive. We will first show that the expectation can change by at most O(ksc0 /8 ) in moving to an
attenuated version of the functions (see Claim 4.3). Then we will show that the error incurred by changing
s(1−3c0 )/8
the distribution to the product distribution of the marginals has absolute value at most 2O(k) 3/2c
ε 0
(see Claim 4.5). This is done by showing that there is a labeling to G that satisfies an s fraction of the
s(1−3c0 )/8
constraints if the error is more than 2O(k) 3/2c .
ε 0
For the rest of the analysis, we write fv and fw instead of fS,v and fS,w , respectively. Let fv =
∑α⊆[2R] fbv (α)χα be the Fourier decomposition of the function and for γ ∈ (0, 1), let T1−γ fv := ∑α⊆[2R] (1−
γ)|α| fbv (α)χα . The following claim is similar to a lemma of Dinur and Kol [8, Lemma 4.11]. The only
difference in the proof is that, we use the smoothness from Property 2 of Theorem 2.5 (which was shown
by Håstad [13, Lemma 6.9]).
Claim 4.3. Let γ := s(c0 +1)/4 ε 1/c0 where c0 is the constant from Theorem 2.5.
k k
E E ∏ fv (xi ) fw (yi ) − E E ∏ T1−γ fv (xi )T1−γ fw (yi ) ≤ O(ksc0 /8 ).
u,v,w T2 u,v,w T2
i=1 i=1
| {z } | {z }
∆0 ∆1
Proof. The claim bounds the change in the expectation when we change the expression ∆0 to ∆1 . The
expression ∆0 is a product of 2k functions and ∆1 is the product of the same functions after applying the
T1−γ operator to each of these functions. We prove the claim by bounding the error with O(sc0 /8 ) when
we add an extra T1−γ operator each time. Thus, the total error will be O(ksc0 /8 ) by doing the telescoping
sum and using the triangle inequality.
For notational convenience, we bound the error when we add the first T1−γ . The effect of adding all
the remaining subsequent T1−γ operators can be analyzed in a similar way.
" # " ! #
k k−1
E E ∏ fv (xi ) fw (yi ) − E E ∏ fv (xi ) fw (yi ) fv (xk )T1−γ fw (yk ) ≤ O(sc0 /8 ). (4.3)
u,v,w T2 u,v,w T2
i=1 i=1
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 15
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
Recall that X,Y denote the matrices chosen by test T2 . Let Y−k be the matrix obtained from Y by removing
the k-th row and F u,v,w (X,Y−k ) := ∏k−1
i=1 f v (xi ) f w (yi ) f v (xk ). Then, Eq. (4.3) can be rewritten as
E E F u,v,w (X,Y−k ) I − T1−γ fw (yk ) ≤ O(sc0 /8 ).
(4.4)
u,v,w T2
Let U be the operator that maps functions on the variable yk , to one on the variables (X,Y−k ) defined by
(U f )(X,Y−k ) := E f (yk ).
yk |X,Y−k
Let Gu,v,w (X,Y−k ) := U(I − T1−γ ) fw (X,Y−k ). Note that E(X,Y )∼T2 Gu,v,w (X,Y−k ) = 0. This is because
E(X,Y )∼T Gu,v,w (X,Y−k ) = E
2 yk ∼{0,1}
\
2L ((I − T1−γ ) f w )(yk ) = ((I − T1−γ ) f w )(0),
/ where the marginal distri-
bution on yk is uniform in {0, 1}2L . Finally, by construction, E(X,Y )∼T2 Gu,v,w (X,Y−k ) = 0 follows, since
fw is an odd function. The domain of Gu,v,w can be thought of as ({0, 1}2k−1 )2dL and the test distribution
on any row is independent across the blocks {Buv (i) ∪ B0uv (i)}i∈[L] . We now think of Gu,v,w as having
domain ∏i∈[L] Ωi where Ωi = ({0, 1}2k−1 )2d corresponds to the set of rows in Buv (i) ∪ B0uv (i). Let the
following be the Efron–Stein decomposition of Gu,v,w with respect to T2 ,
Gu,v,w (X,Y−k ) = ∑ Gu,v,w
α (X,Y−k ).
α⊆[L]
The following technical claim follows from a result similar to [8, Lemma 4.7] and then using [18,
Proposition 2.12]. We defer its proof to Section 4.1. Here we use the role of the random variable c2 in
T2 , which helps to break the perfect correlation between one row and rest of the rows restricted to the
columns Buv (i) ∪ B0uv (i) for all i ∈ [L].
Claim 4.4. For α ⊆ [L]
2
Gαu,v,w ≤ (1 − ε)|α| ∑ 1 − (1 − γ)2|β | fbw (β )2 (4.5)
β ⊆[2R]:πeuw (β )=α
where πeuw (β ) := {i ∈ [L] : ∃ j ∈ [R], ( j ∈ β ∨ j + R ∈ β ) ∧ πuv ( j) = i}.
Substituting the Efron–Stein decomposition of Gu,v,w , F u,v,w into the LHS of Eq. (4.3) gives
E E F u,v,w (X,Y−k ) I − T1−γ fw (yk ) = E E F u,v,w (X,Y−k )Gu,v,w (X,Y−k )
u,v,w T2 u,v,w T2
(by orthonormality of
Efron–Stein decomposition) = E
u,v,w
∑ TE Fαu,v,w (X,Y−k )Gu,v,w
2
α (X,Y−k )
α⊆[L]
s s
(by Cauchy–Schwarz inequality) ≤ E
u,v,w
∑ kFαu,v,w k2 · ∑ kGu,v,w
α k2
α⊆[L] α⊆[L]
s
(Using ∑ kFαu,v,w k2 = kF u,v,w k22 = 1) ≤ E ∑ kGu,v,w
α k2 .
u,w
α⊆[L] α⊆[L]
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 16
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
Using concavity of square root and substituting for kGu,v,w
α k2 from Equation (4.5), we get that the above
is not greater than
v
u
|α| 2|β | b
uE
uu,w ∑ ∑ (1 − ε) 1 − (1 − γ) fw (β )2 .
t α⊆[L] β ⊆[2R]: | {z }
πeuw (β )=α =:Termu,w (α,β )
We will now break the above summation into three different parts and bound each part separately.
Θ0 := E ∑ Termu,w (α, β ), Θ1 := E ∑ Termu,w (α, β ),
u,w u,w
α,β :|α|≥ c1 /4 α,β :|α|< c1 /4
εs 0 εs 0
|β |≤ 1/4 21/c
s ε 0
Θ2 := E ∑ Termu,w (α, β ).
u,w 1
α,β :|α|<
εsc0 /4
2
|β |> 1/4 1/c
s ε 0
1
Upper bound for Θ0 . When |α| > , (1 − ε)|α| < sc0 /4 . Also since fw is {+1, −1} valued, sum
εsc0 /4
of squares of Fourier coefficient is 1. Hence |Θ0 | < sc0 /4 .
2
Upper bound for Θ1 . When |β | ≤ ,
s1/4 ε 1/c0
4 4
1 − (1 − γ)2|β | ≤ 1 − 1 − 1/4 1/c γ = 1/4 1/c γ = 4sc0 /4 .
s ε 0 s ε 0
Again since the sum of squares of Fourier coefficients is 1, |Θ1 | ≤ 4sc0 /4 .
Upper bound for Θ2 . From Property 2 of Theorem 2.5, we have that for any v ∈ V and β with
2
|β | > 1/4 1/c , the probability that |πeuv (β )| < 1/εsc0 /4 , for a random neighbor u, is at most εsc0 /4 .
s ε 0
Hence |Θ2 | ≤ sc0 /4 .
Fix u, v, w chosen by the test. Recall that we thought of fv as having domain ∏i∈[L] Ωi where
Ωi = {0, 1}2d corresponds to the set of coordinates in Buv (i) ∪ B0uv (i). Since the grouping of coordinates
u
depends on u, we define Inf i [ fv ] := Inf i [ fv ] where i ∈ [L] for explicitness. From Equation (2.1),
u
Inf i [ fv ] = ∑ fbv (α)2 ,
α⊆[2dL]:i∈πeuv (α)
where πeuv (α) := {i ∈ [L] : ∃ j ∈ [R], ( j ∈ α ∨ j + R ∈ α) ∧ πuv ( j) = i}.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 17
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
u u
Claim 4.5. Let τu,v,w := ∑i∈[L] Inf i [T1−γ fv ] · Inf i [T1−γ fw ].
" # " # " #
k k k
E E
u,v,w T2
∏ T1−γ fv (xi )T1−γ fw (yi ) − TE ∏ T1−γ fv (xi ) TE ∏ T1−γ fw (yi )
2 2
i=1 i=1 i=1
s
Eu,v,w τu,v,w
≤ 2O(k) .
γ
u
Proof. It is easy to check that ∑i∈[L] Inf i [T1−γ fv ] ≤ 1/γ (c.f., [22, Lemma 1.13]). For any u, v, w, since
the test distribution satisfies the conditions of Theorem 2.9, we get
" # " # " #
k k k r
O(k) τu,v,w
E ∏ T1−γ fv (xi )T1−γ fw (yi ) − E ∏ T1−γ fv (xi ) E ∏ T1−γ fw (yi ) ≤ 2 .
T2 i=1 T2 i=1 T2 i=1 γ
The claim follows by taking expectation over u, v, w and using the concavity of square root.
From Claims 4.5 and 4.3 and using the fact the the marginals of the test distribution T2 on (x1 , . . . , xk )
is the same as marginals on (y1 , . . . , yk ), for γ := s(c0 +1)/4 ε 1/c0 , we get
" # s " #!2
k k
c0 /8 O(k) Eu,v,w τu,v,w
E E
u,v,w X,Y ∈T2
∏ fv (xi ) fw (yi ) ≥ −O(ks )−2
γ
+E E E
u v T2
∏ T1−γ fv (xi ) . (4.6)
i=1 i=1
If τu,v,w in expectation is large, there is a standard way of decoding the assignments to a labeling to
the label cover instance, as shown in Claim 4.6.
Claim 4.6. If G is an at most s-satisfiable instance of L ABEL -C OVER then
s
E τu,v,w ≤ 2 .
u,v,w γ
Proof. Note that ∑α⊆[2R] (1 − γ)|α| fbv (α)2 ≤ 1. We will give a randomized labeling to the L ABEL -C OVER
instance. For each v ∈ V , choose a random α ⊆ [2R] with probability (1 − γ)|α| fbv (α)2 and assign a
uniformly random label j in α to v; if the label j ≥ R, change the label to j − R and with the remaining
probability assign an arbitrary label. For u ∈ U, choose a random neighbor w ∈ V and a random β ⊆ [2R]
with probability (1 − γ)|β | fbw (β )2 , choose a random label ` in β and assign the label πeuw (`) to u. With the
remaining probability, assign an arbitrary label. The fraction of edges satisfied by this labeling is at least
(1 − γ)|α|+|β | b
E ∑ ∑ fv (α)2 fbw (β )2 .
u,v,w
i∈[L] (α,β ):i∈πe (α),i∈πe (β )
|α| · |β |
uv uw
Using the fact that 1/r ≥ γ(1 − γ)r for every r > 0 and γ ∈ [0, 1], we lower bound 1/|α| and 1/|β | by
γ(1 − γ)|α| and γ(1 − γ)|β | , respectively. The above is then not less than
! !
γ2 E ∑
u,v,w
∑ (1 − γ)2|α| fbv (α)2 ∑ (1 − γ)2|β | fbw (β )2 = γ 2 E τu,v,w . u,v,w
i∈[L] α:i∈πeuv (α) β :i∈πeuw (β )
Since G is at most s-satisfiable, the labeling can satisfy at most an s fraction of constraints and the
right-hand side of the above equation is at most s.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 18
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
Lemma 4.2 follows from the above claim and Equation (4.6).
Proof of Theorem 1.2. Using Theorem 2.5, the size of the CSP instance G produced by the reduction is
O(r)
N = nr 22 and the parameter s ≤ 2−d0 r . Setting r = Θ(log log n), gives that N = 2poly log n for a constant
k. Lemma 4.2 and Equation (4.2) imply that
s(1−3c0 )/8 1
O(ksc0 /8 ) + 2O(k) ≥ t .
ε 3/2c0 2 −1
Since k is a constant, this gives that t = Ω(log log n).
For every constant C > 2, by choosing r a large enough constant, we get the hardness result assuming
P 6= NP.
4.1 Proof of Claim 4.4
We will be reusing the notation introduced in the long code test T2 . We denote the k × 2d dimensional
matrix X|B(i)∪B0 (i) by X i and Y |B(i)∪B0 (i) by Y i . Also by X ji , we mean the j-th row of the matrix X i and Y−ki
is the first k − 1 rows of Y . The spaces of the random variables X , X j ,Y−k will be denoted by X , X j , Y−k .
i i i i i i i
Before we proceed to the proof of claim, we need a few definitions and lemmas related to correlated
spaces defined by Mossel [18].
Definition 4.7. Let (Ω1 × Ω2 , µ) be a finite correlated space, the correlation between Ω1 and Ω2 with
respect to µ us defined as
ρ(Ω1 , Ω2 ; µ) := max E [| f (x)g(y)|].
f :Ω1 →R,E[ f ]=0,E[ f 2 ]≤1 (x,y)∼µ
g:Ω2 →R,E[g]=0,E[g2 ]≤1
Definition 4.8 (Markov Operator). Let (Ω1 × Ω2 , µ) be a finite correlated space, the Markov operator,
associated with this space, denoted by U, maps a function g : Ω2 → R to functions Ug : Ω1 → R by the
following map:
(Ug)(x) := E [g(Y ) | X = x].
(X,Y )∼µ
The following results (due to Mossel [18]) provide a way to give an upper bound on the correlation of
correlated spaces.
Lemma 4.9 ([18, Lemma 2.8]). Let (Ω1 × Ω2 , µ) be a finite correlated space. Let g : Ω2 → R be
such that E(x,y)∼µ [g(y)] = 0 and E(x,y)∼µ [g(y)2 ] ≤ 1. Then, among all functions f : Ω1 → R that satisfy
E(x,y)∼µ [ f (x)2 ] ≤ 1, the maximum value of | E[ f (x)g(y)]| is given as:
r
|E[ f (x)g(y)]| = E [(Ug(x))2 ].
(x,y)∼µ
(1) (2)
Proposition 4.10 ([18, Proposition 2.11]). Let (∏ni=1 Ωi × ∏ni=1 Ωi , ∏ni=1 µi ) be a product correlated
(2)
space. Let g : ∏ni=1 Ωi → R be a function and U be the Markov operator mapping functions from
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 19
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
(2) (1)
the space ∏ni=1 Ωi to functions on space ∏ni=1 Ωi . If g = ∑S⊆[n] gS and Ug = ∑S⊆[n] (Ug)S be the
Efron–Stein decompositions of g and Ug, respectively, then,
(Ug)S = U(gS )
i. e., the Efron–Stein decomposition commutes with Markov operators.
Proposition 4.11 ([18, Proposition 2.12]). Assume the setting of Proposition 4.10 and furthermore
(1) (2)
assume that ρ(Ωi , Ωi ; µi ) ≤ ρ for all i ∈ [n]. Then for all g it holds that
kU(gS )k2 ≤ ρ |S| kgS k2 .
We will prove the following claim.
Claim 4.12. For each i ∈ [L], √
ρ Xi × Yi−k , Yik ; T2i ≤ 1 − ε.
Before proving this claim, first let’s see how it leads to the proof of Claim 4.4.
Proof of Claim 4.4. Proposition 4.10 shows that the Markov operator U commutes with taking the Efron–
Stein decomposition. Hence, Gu,v,wα := (U((I − T1−γ ) fw ))α = U((I − T1−γ )( fw )α ), where ( fw )α is the
Efron–Stein decomposition of fw w.r.t. the marginal distribution of T2 on ∏Li=1 Yik , which is a uniform
distribution. Therefore, ( fw )α = ∑ β ⊆[2R], fˆw (β )χβ . Using Proposition 4.11 and Claim 4.12, we have
πeuw (β )=α
√
kGu,v,w
α k22 = kU((I − T1−γ )( fw )α )k22 ≤ ( 1 − ε)2|α| k(I − T1−γ )( fw )α k22
= (1 − ε)|α| ∑ 1 − (1 − γ)2|β | fˆw (β )2 ,
β ⊆[2R]:πeuw (β )=α
where the norms are with respect to the marginals of T2 in the corresponding spaces.
Proof of Claim 4.12. Recall the random variable c2 ∈ {∗, 0, 1} defined in Step 3 of test T2 . Let g and f be
the functions that satisfies E[g] = E[ f ] = 0 and E[g2 ], E[ f 2 ] ≤ 1 such that ρ Xi × Yi−k , Yik ; T2i = E[| f g|].
Define the Markov Operator
Ug(X i ,Y−k
i
)= E [g(Ỹk ) | (X̃, Ỹ−k ) = (X i ,Y−k
i
)].
(X̃,Ỹ )∼T2i
By Lemma 4.9, we have
2
ρ Xi × Yi−k , Yik ; T2i i 2
≤ E [Ug(X i ,Y−k ) ]
T2i
i 2 i 2
= (1 − 2ε) E [Ug(X i ,Y−k ) | c2 = ∗] + ε E [Ug(X i ,Y−k ) | c2 = 0]+
T2i T2i
i 2
ε E [Ug(X i ,Y−k ) | c2 = 1]
T2i
i 2 i 2
≤ (1 − 2ε) + ε E [Ug(X i ,Y−k ) | c2 = 0] + ε E [Ug(X i ,Y−k ) | c2 = 1],
T2i T2i
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 20
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
i )2 | c = ∗] = E[g2 ], which is at most 1. Consider
where the last inequality uses the fact that ETi [Ug(X i ,Y−k
2
2
the case when c2 = 0. By definition, we have
!2
i 2
E [Ug(X i ,Y−k ) | c2 = 0] = E E [g(Ỹk ) | (X̃, Ỹ−k ) = (X i ,Y−k
i
) ∧ c2 = 0] .
T2i X i, (X̃,Ỹ )∼T2i
i ∼T2i
Y−k
Under the conditioning, for any fixed value of X i ,Y−ki , the value of Ỹ | 0
k B (i) is a uniformly random string
whereas Ỹk |B(i) is a fixed string (since the parity of all columns in B(i) is 1). Let U be the uniform
h i i
distribution on {−1, +1}d and P(X i ,Y−k i ) ∈ {+1, −1}d denotes the column wise parities of X |B(i) .
Yi | −k B(i)
i 2
!
h
ii 2 (X̃,Ỹ−k )=(X i ,Y−k
i )∧
E [Ug(X ,Y−k ) | c2 = 0] = E E g(Ỹk ) | c =0
T2i i ∼T i
X i ,Y−k 2 (X̃,Ỹ )∼T2i 2
2
= E E [g(−z, r)]
X i ,Y−k
i ∼T i ,
2
r∼U
z=P(X i ,Y−k
i )
2
= E E [g(z, r)] (since marginal on z is uniform)
z∼U r∼U
!2
= E E ∑ ĝ(α)χα (z, r)
z∼U r∈U
α⊆B(i)∪B0 (i)
!2
= E ∑ ĝ(α) E [χα (z, r)]
z∼U r∈U
α⊆B(i)∪B0 (i)
!2
= E
z∼U
∑ ĝ(α)χα (z) = ∑ ĝ(α)2 .
α⊆B(i) α⊆B(i)
Similarly we have,
i 2
E [Ug(X i ,Y−k
T2i
) | c2 = 1] = ∑ ĝ(α)2 .
α⊆B0 (i)
Now we can bound the correlation as follows.
2
ρ Xi × Yi−k , Yik ; T2i ≤(1 − 2ε) + ε ∑ ĝ(α)2 + ε ∑ ĝ(α)2
α⊆B(i) α⊆B0 (i)
≤(1 − 2ε) + ε ∑ ĝ(α)2 (Using ĝ(φ ) = E[g] = 0)
α⊆B(i)∪B0 (i)
≤(1 − ε). (Using E[g2 ] ≤ 1 and Parseval’s Identity)
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 21
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
5 Improvement to covering hardness of 4-LIN
In this section, we prove Theorem 1.4. We give a reduction from an instance of L ABEL -C OVER,
G = (U,V, E, [L], [R], {πe }e∈E ) as in Definition 2.4, to a 4-LIN-CSP instance G = (V, E). The set of
variables V is V × {0, 1}2R . Any assignment to V is given by a set of functions fv : {0, 1}2R → {0, 1}, for
each v ∈ V . The set of constraints E is given by the following test, which checks whether fv ’s are long
codes of a good labeling to V .
Long Code test T3
1. Choose u ∈ U uniformly and neighbors v, w ∈ V of u uniformly and independently at random.
2. Choose x, x0 , z, z0 uniformly and independently from {0, 1}2R and y from {0, 1}2L . Choose (η, η 0 ) ∈
{0, 1}2L × {0, 1}2L as follows. Independently for each i ∈ [L], set (ηi , ηL+i , ηi0 , ηL+i
0 ) to
(a) (0, 0, 0, 0) with probability 1 − 2ε,
(b) (1, 0, 1, 0) with probability ε and
(c) (0, 1, 0, 1) with probability ε.
3. For y ∈ {0, 1}2L , let y ◦ πuv ∈ {0, 1}2R be the string such that (y ◦ πuv )i := yπuv (i) for i ∈ [R] and
(y ◦ πuv )i := yπuv (i−R)+L otherwise. Given η ∈ {0, 1}2L , z ∈ {0, 1}2R , the string η ◦ πuv · z ∈ {0, 1}2R
is obtained by taking coordinate-wise product of η ◦ πuv and z. Accept iff
fv (x)+ fv (x+y◦πuv +η ◦πuv ·z)+ fw (x0 )+ fw (x0 +y◦πuw +η 0 ◦πuw ·z0 +1) = 1 (mod 2). (5.1)
(Here by addition of strings, we mean the coordinate-wise sum modulo 2.)
Lemma 5.1 (Completeness). If G is an YES instance of L ABEL -C OVER, then there exists f , g such that
each of them covers 1 − ε fraction of E and they together cover all of E.
Proof. Let ` : U ∪ V → [L] ∪ [R] be a labeling to G that satisfies all the constraints. Consider the
assignments given by fv (x) := x`(v) and gv (x) := xR+`(v) for each v ∈ V . On input fv , for any pair of edges
(u, v), (u, w) ∈ E, and x, x0 , z, z0 , η, η 0 , y chosen by the long code test T3 , the LHS in Eq. (5.1) evaluates to
0 0 0
x`(v) + x`(v) + y`(u) + η`(u) z`(v) + x`(w) + x`(w) + y`(u) + η`(u) z0`(w) + 1 = η`(u) z`(v) + η`(u)
0
z0`(w) + 1.
0
Similarly for gv , the expression evaluates to ηL+`(u) zR+`(v) + ηL+`(u) z0R+`(w) + 1. Since (ηi , ηi0 ) = (0, 0)
with probability 1 − ε, each of f , g covers 1 − ε fraction of E. Also for i ∈ [L] whenever (ηi , ηi0 ) = (1, 1),
0 ) = (0, 0) and vice versa. So one of the two evaluations above is 1 (mod 2). Hence the pair
(ηL+i , ηL+i
of assignments f , g cover E.
Lemma 5.2 (Soundness). Let c0 be the constant from Theorem 2.5. If G is at most s-satisfiable with
s < δ 10/c0 +5/4, then any independent set in G has fractional size at most δ .
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 22
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
Proof. Let I ⊆ V be an independent set of fractional size δ in the constraint graph G. For every variable
v ∈ V , let fv : {0, 1}2R → {0, 1} be the indicator function of the independent set restricted to the vertices
that correspond to v. Since I is an independent set, we have
fv (x) fv (x + y ◦ πuv + η ◦ πuv · z) fw (x0 ) fw (x0 + y ◦ πuw + η 0 ◦ πuw · z0 + 1) = 0.
E E0 (5.2)
u,v,w x,x ,
z,z0 ,
η,η 0 ,y
For α ⊆ [2R], let πuv⊕ (α) ⊆ [2L] be the set containing elements i ∈ [2L] such that if i < L there are an odd
number of j ∈ [R] ∩ α with πuv ( j) = i and if i ≥ L there are an odd number of j ∈ ([2R] \ [R]) ∩ α with
πuv ( j − R) = i − L . It is easy to see that χα (y ◦ πuw ) = χπuv⊕ (α) (y). Expanding fv in the Fourier basis and
taking expectation over x, x0 and y, we get that
fbv (α)2 fbw (β )2 (−1)|β | χα (η ◦ πuv · z)χβ (η 0 ◦ πuw · z0 ) = 0.
E ∑ E (5.3)
u,v,w ⊕ ⊕ z,z0 ,η,η 0
α,β ⊆[2R]:πuv (α)=πuw (β )
Now the expectation over z, z0 simplifies as
E ∑ fbv (α)2 fbw (β )2 (−1)|β | Pr 0 [α · (η ◦ πuv ) = β · (η 0 ◦ πuw ) = 0̄] = 0, (5.4)
u,v,w ⊕ ⊕ η,η
α,β ⊆[2R]:πuv (α)=πuw (β ) | {z }
=:Termu,v,w (α,β )
where we think of α, β as the characteristic vectors in {0, 1}2R of the corresponding sets. We will now
break up the above summation into different parts and bound each part separately. For a projection
π : [R] → [L], define πe(α) := {i ∈ [L] : ∃ j ∈ [R], ( j ∈ α ∨ j + R ∈ α) ∧ (π( j) = i)}. We divide the space
of (α, β ) into 4 sets as follows.
⊕ ⊕
E0 := (α, β ) πuv (α) = πuw (β ) = 0/ ,
n o
⊕ ⊕
E1 := (α, β ) πuv (α) = πuw / max{|α|, |β |} ≤ 2/δ 5/c0 ,
(β ) 6= 0,
⊕ ⊕
/ max{|πeuv (α)|, |πeuw (β )|} ≥ 1/δ 5 ,
E2 := (α, β ) πuv (α) = πuw (β ) 6= 0,
n o
⊕ ⊕
E3 := (α, β ) πuv (α) = πuw / max{|α|, |β |} > 2/δ 5/c0 , max{|πeuv (α)|, |πeuw (β )|} < 1/δ 5 .
(β ) 6= 0,
And define the following quantities for i ∈ {0, 1, 2, 3}.
Θi := ∑ E Termu,v,w (α, β ) .
u,v,w
(α,β )∈Ei
⊕ (β ) = 0,
Lower bound for Θ0 . If πuw / then |β | is even. Hence, all the terms in Θ0 are positive and
2 4
Θ0 ≥ E Termu,v,w (0, 0) = E E fbv (0)2 ≥ E fbv (0) = δ 4 .
u,v,w u v u,v
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 23
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
Upper bound for Θ1 . Consider the following strategy for labeling vertices u ∈ U and v ∈ V . For u ∈ U,
pick a random neighbor v, choose α with probability fbv (α)2 and set its label to a random element in
πeuv (α). For w ∈ V , choose β with probability fbw (β )2 and set its label to a random element of β . If the
label j ≥ R, change the label to j − R. The probability that a random edge (u, w) of the label cover is
satisfied by this labeling is
1 δ 10/c0
E ∑ fbv (α)2 fbw (β )2 ≥ E ∑ fbv (α)2 fbw (β )2
u,v,w
α,β :
|πuv (α)| · |β | u,v,w
e α,β :
4
πeuv (α)∩πeuw (β )6=0/ ⊕ (α)=π ⊕ (β )6=0
πuv /
uw
max{|α|,|β |}≤2/δ 5/c0
δ 10/c0
≥ |Θ1 | · .
4
Since the instance is at most s-satisfiable, the above is not greater than s. Choosing s < δ 10/c0 +5/4, will
imply |Θ1 | ≤ δ 5 .
Upper bound for Θ2 . Suppose |πeuv (α)| ≥ 1/δ 5 , then note that
5
Pr 0 [α · (η ◦ πuv ) = β · (η 0 ◦ πuw ) = 0] ≤ Pr[α · (η ◦ πuv ) = 0] ≤ (1 − ε)|πeuv (α)| ≤ (1 − ε)1/δ .
η,η η
Since the sum of squares of Fourier coefficients of f is less than 1 and ε is a constant, we get that
5
|Θ2 | ≤ 1/2Ω(1/δ ) < O(δ 5 ).
Upper bound for Θ3 . From the third property of Theorem 2.5, we have that for any v ∈ V and α ⊆ [2R]
with |α| > 2/δ 5/c0 , the probability that |πeuv (α)| < 1/δ 5 , for a random neighbor u of v, is at most δ 5 .
Hence |Θ3 | ≤ δ 5 .
On substituting the above bounds in Equation (5.4), we get that δ 4 − O(δ 5 ) ≤ 0, which gives a
contradiction for small enough δ . Hence there is no independent set in G of size δ .
Proof of Theorem 1.4. From Theorem 2.5, the size of the CSP instance G produced by the reduction is
O(r)
N = nr 22 and the parameter s ≤ 2−d0 r . Setting r = Θ(log log n), gives that N = 2poly log n and the size
of the largest independent set δ = 1/ poly log n = 1/ poly log N.
6 Invariance Principle for correlated spaces
Theorem 2.9 (Invariance Principle for correlated spaces) [Restated] Let (Ωk1 × Ωk2 , µ) be a correlated
probability space such that the marginal of µ on any pair of coordinates one each from Ω1 and Ω2
is a product distribution. Let µ1 , µ2 be the marginals of µ on Ωk1 and Ωk2 , respectively. Let X,Y be
two random k × L dimensional matrices chosen as follows. Independently for every i ∈ [L], the pair of
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 24
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
columns (xi , yi ) ∈ Ωk1 × Ωk2 is chosen from µ. Let xi , yi denote the i-th rows of X and Y , respectively. If
F : ΩL1 → [−1, +1] and G : ΩL2 → [−1, +1] are functions such that
s s s
τ := ∑ Inf i [F] · Inf i [G] and Γ := max ∑ Inf i [F], ∑ Inf i [G] ,
i∈[L] i∈[L] i∈[L]
then " # " # " #
E ∏ F(xi )G(yi ) − X∈µE ∏ F(xi ) Y ∈µE ∏ G(yi ) ≤ 2O(k) Γτ. (6.1)
(X,Y )∈µ ⊗L i∈[k]
⊗L
1 i∈[k]
⊗L
2 i∈[k]
Proof. We will prove the theorem by using the hybrid argument. For i ∈ [L + 1], let X (i) ,Y (i) be distributed
according to (µ1 ⊗ µ2 )⊗i ⊗ µ ⊗L−i . Thus, (X (0) ,Y (0) ) = (X,Y ) is distributed according to µ ⊗L while
(X (L) ,Y (L) ) is distributed according to (µ1 ⊗ µ2 )⊗L . For i ∈ [L], define
" # " #
k k
(i) (i) (i+1) (i+1)
erri := E ∏ F(x j )G(y j ) − E ∏ F(x j )G(y j ) . (6.2)
X (i) ,Y (i) j=1 X (i+1) ,Y (i+1) j=1
The left-hand side of Equation (2.2) is not greater than ∑i∈[L] erri . Now for a fixed i, we will bound
erri . We use the Efron–Stein decomposition of F, G to split them into two parts: the part that depends on
the i-th input and the part independent of the i-th input.
F = F0 + F1 where F0 := ∑ Fα and F1 := ∑ Fα .
α:i∈α
/ α:i∈α
G = G0 + G1 where G0 := ∑ Gβ and G1 := ∑ Gβ .
β :i∈β
/ β :i∈β
Note that Inf i [F] = kF1 k22 and Inf i [G] = kG1 k22 . Furthermore, the functions F0 and F1 are bounded since
0 0
F0 (x) = Ex0 [F(x )|x[L]\i = x[L]\i ] ∈ [−1, +1] and F1 (x) = F(x) − F0 (x) ∈ [−2, +2]. For a ∈ {0, 1}k , let
Fa (X) := ∏kj=1 Fa j (x j ). Similarly G0 , G1 are bounded and Ga defined analogously. Substituting these
definitions in Equation (6.2) and expanding the products gives
h i h i
erri = ∑ E Fa (X (i) )Gb (Y (i) ) − E Fa (X (i+1) )Gb (Y (i+1) ) .
a,b∈{0,1}k X (i) ,Y (i) X (i+1) ,Y (i+1)
Since both the distributions are identical on (Ωk1 )⊗L and (Ωk2 )⊗L , all terms with a = 0̄ or b = 0̄ are zero.
For instance when a = 0̄, Fa does not depend on the i-th coordinate. Therefore, in both the distributions
(X (i) ,Y (i) ) and (X (i+1) ,Y (i+1) ), the i-th column of X can be dropped. Now, the distributions of Y (i) and
Y (i+1) are identical conditioned on the X with the i-th column dropped. Thus, the expectation is 0.
Since µ is uniform on any pair of coordinates on each from the Ω1 and Ω2 sides, terms with
|a| = |b| = 1 also evaluates to zero using a similar argument as above. Now consider the remaining terms
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 25
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
with |a|, |b| ≥ 1, |a| + |b| > 2. Consider one such term where a1 , a2 = 1 and b1 = 1. In this case, by the
Cauchy–Schwarz inequality we have that
h i q
(i−1) (i−1)
E Fa (X )Gb (Y ) ≤ E F1 (x1 )2 G1 (y1 )2 · kF1 k2 · ∏ Fa j · ∏ Gb . j
X (i−1) ,Y (i−1) j>2 j>1
∞ ∞
From the facts that the marginal of µ to any pair of coordinates one each from Ω1 and Ω2 sides are
uniform, Inf i [F] = kF1 k22 and |F0 (x)|, |F1 (x)|, |G0 (x)|, |G1 (x)| are all bounded by 2, the right side of above
becomes
q q q
E F1 (x1 )2 E G1 (y1 )2 · kF1 k2 · ∏ Fa j · ∏ Gb j ≤ Inf i [F]2 Inf i [G] · 22k .
j>2 ∞ j>1 ∞
All the other terms corresponding to other pairs (a, b), which are at most 22k in number, are bounded
analogously. Hence,
q q
4k 2 2
∑ erri ≤ 2 ∑ Inf i [F] Inf i [G] + Inf i [F]Inf i [G]
i∈[L] i∈[L]
p p p
= 24k ∑ Inf i [F]Inf i [G] Inf i [F] + Inf i [G] .
i∈[L]
Applying the Cauchy–Schwarz inequality, followed by a triangle inequality, we obtain
s s s
∑ erri ≤ 24k ∑ Inf i [F]Inf i [G] ∑ Inf i [F] + ∑ Inf i [G] .
i∈[L] i∈[L] i∈[L] i∈[L]
This completes the proof.
References
[1] S ANJEEV A RORA , C ARSTEN L UND , R AJEEV M OTWANI , M ADHU S UDAN , AND M ARIO
S ZEGEDY: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555,
1998. Preliminary version in FOCS’92. [doi:10.1145/278298.278306, ECCC:TR98-008] 8
[2] S ANJEEV A RORA AND S HMUEL S AFRA: Probabilistic checking of proofs: A new char-
acterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92.
[doi:10.1145/273865.273901] 8
[3] 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, ECCC:TR08-009] 5
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 26
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
[4] N IKHIL BANSAL AND S UBHASH K HOT: Inapproximability of hypergraph vertex cover and
applications to scheduling problems. In Proc. 37th Internat. Colloq. Automata, Lang., Programming
(ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22] 5, 11
[5] B OAZ BARAK , PARIKSHIT G OPALAN , J OHAN H ÅSTAD , R AGHU M EKA , P RASAD R AGHAVEN -
DRA , AND DAVID S TEURER : Making the long code shorter. SIAM J. Comput., 44(5):1287–1324,
2015. Preliminary version in FOCS’12. [doi:10.1137/130929394, arXiv:1111.0405, ECCC:TR11-
142] 7
[6] A MEY B HANGALE , P RAHLADH H ARSHA , AND G IRISH VARMA: A characterization of hard-to-
cover CSPs. In Proc. 30th Comput. Complexity Conf. (CCC’15), pp. 280–303. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.CCC.2015.280, arXiv:1411.7747]
1
[7] I RIT D INUR AND V ENKATESAN G URUSWAMI: PCPs via the low-degree long code and hardness
for constrained hypergraph coloring. Israel J. Math., 209:611–649, 2015. Preliminary version in
FOCS’13. [doi:10.1007/s11856-015-1231-3, ECCC:TR13-122] 7
[8] I RIT D INUR AND G ILLAT KOL: Covering CSPs. In Proc. 28th IEEE Conf. on Comput. Complexity
(CCC’13), pp. 207–218. IEEE Comp. Soc., 2013. [doi:10.1109/CCC.2013.29, ECCC:TR12-088] 2,
3, 4, 5, 8, 11, 13, 15, 16
[9] U RIEL F EIGE AND J OE K ILIAN: Zero knowledge and the chromatic number. J. Comput. System
Sci., 57(2):187–199, 1998. Preliminary version in CCC’96. [doi:10.1006/jcss.1998.1587] 2
[10] V ENKAT G URUSWAMI , P RAHLADH H ARSHA , J OHAN H ÅSTAD , S RIKANTH S RINIVASAN , AND
G IRISH VARMA: Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.
SIAM J. Comput., 46(1):132–159, 2017. Preliminary version in STOC’14. [doi:10.1137/140995520,
arXiv:1311.7407] 7
[11] V ENKATESAN G URUSWAMI , J OHAN H ÅSTAD , AND M ADHU S UDAN: Hardness of approximate
hypergraph coloring. SIAM J. Comput., 31(6):1663–1686, 2002. Preliminary version in FOCS’00.
[doi:10.1137/S0097539700377165] 2, 5
[12] V ENKATESAN G URUSWAMI AND E UIWOONG L EE: Strong inapproximability results on balanced
rainbow-colorable hypergraphs. Combinatorica, 38(3):547–599, 2018. Preliminary version in
SODA’15. [doi:10.1007/s00493-016-3383-0, ECCC:TR14-043] 6, 10
[13] 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] 8, 15
[14] J ONAS H OLMERIN: Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 − ε. In
Proc. 34th STOC, pp. 544–552. ACM Press, 2002. [doi:10.1145/509907.509986, ECCC:TR01-094]
5
1/10−o(1)
[15] S ANGXIA H UANG: 2(log N) hardness for hypergraph coloring. 2015. [arXiv:1504.03923] 7
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 27
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
[16] S UBHASH K HOT AND R ISHI S AKET: Hardness of coloring 2-colorable 12-uniform hypergraphs
Ω(1)
with 2(log n) colors. SIAM J. Comput., 46(1):235–271, 2017. Preliminary version in FOCS’14.
[doi:10.1137/15100240X, ECCC:TR14-051] 7
[17] M ICHAEL K RIVELEVICH , R AM NATHANIEL , AND B ENNY S UDAKOV: Approximating coloring
and maximum independent sets in 3-uniform hypergraphs. J. Discr. Algor., 41(1):99–113, 2001.
Preliminary version in SODA’01. [doi:10.1006/jagm.2001.1173] 2
[18] E LCHANAN M OSSEL: Gaussian bounds for noise correlation of functions. Geom. Funct. Anal.,
19(6):1713–1756, 2010. Preliminary version in FOCS’08. [doi:10.1007/s00039-010-0047-x,
arXiv:math/0703683] 6, 9, 16, 19, 20
[19] R AN R AZ: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary
version in STOC’95. [doi:10.1137/S0097539795280895] 8
[20] R ISHI S AKET: Hardness of finding independent sets in 2-colorable hypergraphs and of satisfiable
CSPs. In Proc. 29th IEEE Conf. on Comput. Complexity (CCC’14), pp. 78–89. IEEE Comp. Soc.,
2014. [doi:10.1109/CCC.2014.16, arXiv:1312.2915] 7
[21] G IRISH VARMA: Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions.
Chicago J. Theoret. Comp. Sci., (3):1–8, 2015. [doi:10.4086/cjtcs.2015.003, arXiv:1408.0262] 7
[22] C ENNY W ENNER: Circumventing d-to-1 for approximation resistance of satisfiable predicates
strictly containing parity of width at least four. Theory of Computing, 9(23):703–757, 2013.
Preliminary version in APPROX’12. [doi:10.4086/toc.2013.v009a023, ECCC:TR12-145] 6, 10, 18
[23] DAVID Z UCKERMAN: Linear degree extractors and the inapproximability of max clique and
chromatic number. Theory of Computing, 3(6):103–128, 2007. Preliminary version in STOC’06.
[doi:10.4086/toc.2007.v003a006, ECCC:TR05-100] 2
AUTHORS
Amey Bhangale
Assistant professor
University of California, Riverside
California, USA
ameyb ucr edu
https://www.cs.ucr.edu/~bhangale/
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 28
A C HARACTERIZATION OF H ARD - TO -C OVER CSP S
Prahladh Harsha
Associate professor
Tata Institute of Fundamental Research,
Mumbai, India
prahladh tifr res in
http://www.tcs.tifr.res.in/~prahladh/
Girish Varma
Assistant professor
International Institute of Information Technology (IIIT),
Hyderabad, India
girish.varma iiit ac in
https://girishvarma.in
ABOUT THE AUTHORS
A MEY B HANGALE is an Assistant Professor in the Computer Science Department at the
University of California, Riverside.
Amey got his undergraduate degree from VJTI, Mumbai. In the final year of his under-
graduate studies, he met Prof. Rajiv C. Gandhi, who was visiting Mumbai in 2010/11 on
a Fulbright scholarship and taught a course on approximation algorithms at VJTI. This
encounter influenced Amey to pursue research in the theory of computing.
Amey graduated from Rutgers University in 2017 under the supervision of Swastik
Kopparty. He spent two wonderful years in Israel where he was a post-doctoral fellow at
the Weizmann Institute of Science hosted by Irit Dinur. He is interested in approximation
algorithms, hardness of approximations and analysis of Boolean functions. He enjoys
playing and watching tennis (and hardly says no to anyone who invites him to play
tennis).
P RAHLADH H ARSHA is a theoretical computer scientist at the Tata Institute of Fundamental
Research (TIFR). He received his B. Tech. degree in Computer Science and Engineering
from the IIT Madras in 1998 and his S. M. and Ph. D. degrees in Computer Science from
MIT in 2000 and 2004, respectively. Prior to joining TIFR in 2010, he was at Microsoft
Research, Silicon Valley and at the Toyota Technological Institute at Chicago. His areas
of interest include computational complexity, hardness of approximation, coding theory
and information theory. Prahladh credits his mother for his interest in mathematics and
dance. He is also deeply indebted to U Koteswara Rao, his high school mentor, for
exposing him to both the beauty and rigour in mathematics.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 29
A MEY B HANGALE , P RAHLADH H ARSHA AND G IRISH VARMA
G IRISH VARMA is a scientist at the Machine Learning Lab at IIIT Hyderabad. He received
his B. Tech. degree in Computer Science and Engineering from the NIT Calicut in
2008 and his M. S. and Ph. D. degrees in Computer Science from the Tata Institute of
Fundamental Research (TIFR), Mumbai in 2015. Prior to joining IIIT Hyderabad in
2016, he was at the Weizmann Institute of Science. His research focusses on using
theoretical computer science concepts in solving applied problems in computer vision.
T HEORY OF C OMPUTING, Volume 16 (16), 2020, pp. 1–30 30