Hardness of Approximate Hypergraph Coloring.
We introduce the notion of covering complexity of a verifier for probabilistically checkable proofs (PCPs). Such a verifier is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The verifier is also given a random string and decides whether to accept the proof or not, based on the given random string. We define the covering complexity of such a verifier, on a given input, to be the minimum number of proofs needed to "satisfy" the verifier on every random string; i.e., on every random string, at least one of the given proofs must be accepted by the verifier.  The covering complexity of PCP verifiers offers a promising route to getting stronger inapproximability results for some minimization problems and, in particular, (hyper)graph coloring problems.  We present a PCP verifier for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a superconstant covering complexity for statements not in the language. Moreover, the acceptance predicate of this verifier is a simple not-all-equal check on the four bits it reads. This enables us to prove that, for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors and also yields a superconstant inapproximability result under a stronger hardness assumption.
Introduction
The study of probabilistically checkable proof (PCP) systems has led to major breakthroughs in
theoretical computer science in the past decade. In particular this study has led to a surprisingly
clear understanding of the complexity of nding approximate solutions to optimization problems.
A recurring theme in this study is the association of new complexity measures to veriers of PCP
systems, and construction of e-cient veriers under the new measure. The new measures are
then related to some special subclass of optimization problems to gain new insight about the
approximability of problems in this subclass of optimization problems. This paper presents yet
another such complexity measure, the covering complexity of a verier, and relates it to a subclass
of optimization problems, namely hypergraph coloring problems. Below we elaborate on some of
the notions above, such as PCP, approximability, hypergraph coloring, and introduce our new
complexity measure.
Probabilistically checkable proofs. The centerpiece of a PCP system is the probabilistic veri-
er. This verier is a randomized polynomial time algorithm whose input is a \theorem", and who
is also given oracle access to a \proof". Using the traditional equivalence associated with randomized
algorithms, it is convenient to think of the verier as having two inputs, the \theorem" and a
\random string". Based on these two inputs the verier settles on a strategy to verify the proof |
namely, it decides on a sequence of queries to ask the oracle, and prepares a predicate P . It then
queries the oracle and if it receives as response bits a applies the predicate P (a
and accepts i the predicate is satised. 1 The quality of the PCP system is roughly related to its
ability to distinguish valid proofs (true \theorems" with correct \proofs") from invalid theorems
(incorrect \theorems" from any purported \proof") | hopefully the verier accepts valid proofs
with much higher probability than it does invalid theorems.
To study the power of PCP systems in a complexity-theoretic setting, we quantify some of the
signicant resources of the verier above, and then study the resources needed to verify proofs of
membership for some hard language. Fix such a language L and consider a verier V whose goal is
to verify proofs of membership in L. The above paragraph already hints at four measures we may
associate with such a verier and we dene them in two steps. For functions
say that a V is (r; q)-restricted if, on input x (implying the theorem x 2 L) of length n,
a random string of length r(n) and makes q(n) queries to the proof oracle. We say that veries
L with completeness c and soundness s, if (1) For every x 2 L, there exists an oracle  such that
V , on input x and oracle access to , outputs accept with probability at least c, and (2) For every
x 62 L and every oracle , V outputs accept with probability at most s. The class of all languages
L that have an (r; q)-restricted verier verifying it with completeness c and soundness s is denoted
Covering Complexity. In the variant of PCPs that we consider here, we stick with (r; q)-
restricted veriers, but alter the notion of completeness and soundness. Instead of focusing on the
one proof that maximizes the probability with which the verier accepts a given input, here we
allow multiple proofs to be provided to the verier. We say that a set of proofs f covers
a verier V on input x if for every random string, there exists one proof  i such that V accepts
i on this random string. We are interested in the smallest set of proofs that satisfy this property
and the cardinality of this set is said to be the covering complexity of the verier on this input.
This description of a verier is somewhat restrictive. More general denitions allow the verier to be adaptive,
deciding on later queries based on response to previous ones. For this paper, the restricted version su-ces.
Analogous to the class PCP, we may dene the class cPCP c;s [r; q] (for covering PCP) to be the class
of all languages for which there exist (r; q)-restricted veriers that satisfy the following conditions:
(Completeness) If x 2 L, the covering complexity of V on x is at most 1=c. (Soundness) If x 62 L
then the covering complexity of V on x is at least 1=s.
Notions somewhat related to covering complexity have been considered in the literature implicitly
and explicitly in the past. Typically these notions have been motivated by the approximability
of minimization problems, such as graph coloring, set cover, and the closest vector problem. Our
specic notion is motivated by graph and hypergraph coloring problems. We describe our motivation
next. We defer the comparison with related notions to later in this section.
Hypergraph coloring, approximability, and inapproximability. An l-uniform hypergraph
H is given by a set of vertices V and a set of edges E where an edge e 2 E is itself a subset of
V of cardinality l. A k-coloring of H is a map from V to the set kg such that no edge
is monochromatic. The hypergraph coloring problem is that of nding, given H, the smallest k
for which a k-coloring of H exists. When l = 2, then the hypergraph is just a graph, and the
hypergraph coloring problem is the usual graph coloring problem.
Graph and hypergraph coloring problems have been studied extensively in the literature from
both the combinatorial and algorithmic perspective. The task of determining if a l-uniform graph
is k-colorable is trivial if almost so if l 2. Every other case turns out to
be NP-hard. The case of l = 2, k  3 is a classical NP-hard problem, while the case of
was shown NP-hard by Lovasz [23]. Thus, even the property of a hypergraph being 2-colorable is
non-trivial. This property, also called Property B, has been studied in the extremal combinatorics
literature for long. Much work has been done on determining su-cient conditions under which a
hypergraph family is 2-colorable and on solving the corresponding algorithmic questions [11, 6, 7,
25, 26, 29, 27].
The hardness of the coloring problem motivates the study of the approximability of the graph and
hypergraph coloring problems. In context of these problems, an (l; k; k 0 )-approximation algorithm
is one that produces (in polynomial time) a k 0 -coloring of every k-colorable l-uniform hypergraph
for some k 0 > k, with the \approximation" being better as k 0 gets closer to k. Even this problem
turns out to be non-trivial, with the best known algorithms for coloring even 3-colorable graphs
requiring
colors [9, 19], where n is the number of vertices. Similarly, inspired in part by
the approximate graph coloring algorithms, several works [1, 10, 22] have provided approximation
algorithms for coloring 2-colorable hypergraphs. The best known result for 2-colorable 4-uniform
hypergraphs is a polynomial time coloring algorithm that uses ~
O(n 3=4 ) colors [1, 10].
To justify the intractability of the approximation versions of the hypergraph coloring problem,
one looks for inapproximability results. Inapproximability results show that it is NP-hard to achieve
the goals of an (l; k; k 0 )-approximation algorithm by producing a polynomial time computable
reduction from, say, SAT to a \gap" problem related to hypergraph coloring. Here we assume
a conservative denition of such a reduction, namely, the many-one reduction. The many-one
version of such a reduction would reduce a formula ' to an l-uniform hypergraph H such that
H is k-colorable if ' is satisable, and H is not k 0 -colorable if ' is not satisable. Since the
existence of an (l; k; k 0 )-approximation algorithm now gives the power to decide if ' is satisable
or not, this shows that the approximation problem is NP-hard. In the sequel, when we say that an
)-approximation problem is NP-hard, we always implicitly mean that the \gap version" of
the problem is NP-hard.
This methodology combined with the PCP technique has been employed heavily to get hardness
results of graph coloring problems. This approach started with the results of [24], and culminates
with, essentially tight, the results of [12] who show that the (2;
is NP-hard under randomized reductions. However, for graphs whose chromatic number is a small
constant, the known hardness results are much weaker. For example, for 3-colorable graphs the best
known hardness result only rules out coloring using 4 colors [20, 16]. This paper is motivated by the
quest for strong (super-constant) inapproximability for coloring graphs whose chromatic number is
a small constant. We do not get such results for graph coloring, but do get such inapproximability
results for hypergraph coloring and in particular for coloring 4-uniform hypergraphs.
Graph coloring and covering PCPs. In examining the reasons why the current techniques
have been unable to show strong hardness results for inapproximability of coloring 3-colorable
graphs, a natural question arises: Are PCPs really necessary to show such hardness results, or
would something weaker su-ce? To date there are no reasons showing PCPs are necessary. And
while the rst result showing the intractability of coloring 3-colorable graphs with 4 colors [20] did
use the PCP technique, [16] show that PCPs are not needed in this result. The starting point of our
work is the observation that covering PCPs are indeed necessary for showing strong hardness results
for graph coloring. Specically, in Proposition 2.1, we show that if the (2; c; !(1))-approximation
problem for coloring is NP-hard for c < 1, then NP  cPCP
results can also be derived from hardness results for coloring hypergraphs, though we don't do so
here.)
Previous approaches have realized this need implicitly, but relied on deriving the required results
via PCPs. In particular, they use the trivial containment PCP 1;s [r; q]  cPCP 1;s [r; q] and build
upon the latter result to derive hardness for coloring. (Notice, that we do not have such a simple
containment when the completeness parameter is not equal to 1. This special case of
important in general and is referred to as perfect completeness.) For our purposes, however, this
trivial containment is too weak. In particular it is known that PCP c;s [log; q]  P for every c; s; q
such that c > s2 q (cf. [8, Lemma 10.6]). Thus it is not possible to show NP  cPCP
for any constant
> 0, using the trivial containment mentioned above (and such a covering
PCP is essential for super-constant hardness results for coloring hypergraphs). Thus it becomes
evident that a direct construction of covering PCPs may be more fruitful and we undertake such
constructions in this paper.
Related Notions. Typically, every approach that applies PCP to minimization problems has
resulted, at least implicitly, in some new complexity measures. Two of those that are close to,
and likely to be confused with, the notion of covering complexity are the notions of \multiple
assignments" [2], and the \covering parameter" of [12]. Here we clarify the distinctions.
In the former case, the multiple assignments of [2], the proof oracle is expected to respond
to each query with an element of a large alphabet (rather than just a bit). When quantifying
the \quality" of a proof, however, the oracle is allowed to respond with a subset of the alphabet,
rather than just a single element, and the goal of the prover is to pick response sets of small sizes
so that on every random string, the verier can pick one elements from each response set to the
dierent queries so that it leads to acceptance. Once again we have a notion of covering all random
strings with valid proofs, but this time the order of quantiers is dierent. The notion of multiple
assignments is interesting only when the alphabet of the oracles responses are large, while our
notion remains interesting even when the oracle responds with an element of a binary alphabet.
The second related notion is the covering parameter of Feige and Kilian [12]. Since the names
are confusingly similar (we apologize for not detecting this at an early stage), we refer to their notion
as the FK-covering parameter. In a rather simplied sense, their parameter also allows multiple
proofs to be presented to the verier. But their notion of coverage requires that on every random
string and every possible accepting pattern of query responses for the verier, there should exist a
proof which gives this accepting pattern (and is hence accepted). For any xed verier and input,
the FK-covering number is always larger than ours, since we don't need every accepting pattern
to be seen among the proofs. Though the notions appear close, the motivation, the application,
and the technical challenges posed by the FK-covering parameter and ours are completely dierent.
Both notions arise from an attempt to study graph coloring, but their focus is on general graphs
(with high chromatic number), while ours is on graphs of small chromatic number. In their case,
separation of the FK-covering parameter is su-cient, but not necessary, to give inapproximability
of coloring. For our parameter, separation is necessary, but not su-cient to get the same. Finally,
in their constructions the challenge is to take a traditional PCP and enhance it to have small FK-
covering completeness and they use the PCP directly to argue that the soundness is not large. In
our case, the completeness is immediate and the soundness needs further analysis.
Gadgets and covering complexity. Returning to our notion of covering complexity, while it
seems essential to study this to get good hardness results on coloring, the reader should also be
warned that this notion is somewhat less robust that usual notions that one deals with in PCPs.
Specically, prior notions were not very sensitive to the predicate applied by the verier in deciding
its nal output. They could quantify the power of the verier by simple parameters such as number
of bits read, or number of accepting congurations. Here we are forced to pay attention to the
verier's computations and restrict these to get interesting results. It is reasonable to ask why this
happens and we attempt to give some justication below.
In standard PCPs, it is often possible to use \gadgets" (whenever they are available) to convert
the acceptance predicate of the verier from one form to another, for only a small loss in the
performance. For example suppose one has a PCP verier V 1 that reads three bits of a proof and
accepts if they are not all equal (NAE). Such a verier would directly prove the hardness of the
\Max NAE-3SAT" problem. But by application of a gadget the same verier can be transformed
into one that proves the hardness of the \Max 3SAT" problem. The gadget notices that the
function NAE(a; b; c) for three Boolean variables a; b; c is simply (a _ b _ c) ^ (:a _:b_:c), which
is a conjunction of two 3SAT clauses. Thus a transformed verier V 2 which picks three bits of
the proof as V 1 does, and then picks one of the two clauses implied by the check performed by V 1
and veries just this one clause, is now a verier whose acceptance predicate is a 3SAT condition.
Furthermore, if the acceptance probability of V 1 on the same proof is 1 , then the acceptance
probability of V 2 on some given proof is exactly 1 =2. Thus if V 1 proves inapproximability of
proves inapproximability of Max 3SAT.
Unfortunately, a similar transformation does not apply in the case of covering complexity.
Notice that two proofs, the oracle that always responds with 0 and the one that responds with 1,
always su-ces to cover any verier whose acceptance predicate is 3SAT. Yet there exist NAE 3-
SAT veriers that can not be covered by any constant number of proofs. (For example, the verier
that picks 3 of the n bits of the proof uniformly and independently at random and applies the
NAE 3-SAT predicate to them, needs
eds n) proofs to be covered.) Thus even though a gadget
transforming NAE 3SAT to 3SAT does exist, it is of no use in preserving covering complexity of
veriers. This non-robust behavior of cPCP veriers forces us to be careful in designing our veriers
and our two results dier in mainly the predicate applied by the verier.
Our results. Our rst result is a containment of NP in the class cPCP 1;" [O(log n); 4], for every
" > 0. If the randomness is allowed to be slightly super-logarithmic, then the soundness can be
reduced to some explicit o(1) function. Technically, this result is of interest in that it overcomes
the qualitative limitation described above of passing through standard PCPs. Furthermore, the
proof of this result is also of interest in that it shows how to apply the (by now) standard Fourier-
analysis based techniques to the studying of covering complexity as well. Thus it lays out the hope
for applying such analysis to other cPCP's as well.
Unfortunately, the resulting cPCP fails to improve inapproximability of graph coloring or even
hypergraph coloring. As noted earlier covering PCPs are only necessary, but not su-cient to get
hardness results for hypergraph coloring. In order to get hardness results for hypergraph coloring
from covering PCPs, one needs veriers whose acceptance condition is a NAE SAT (not-all-equal)
predicate (though, in this case, it is also reasonable to allow the responses of the queries to be
elements of a non-binary alphabet, and a result over q-ary alphabet will give a result for q-colorable
hypergraphs).
Keeping this objective in mind, we design a second verier (whose query complexity is also
4 bits), but whose acceptance predicate simply checks if the four queried bits are not all equal.
The verier has perfect completeness and its covering soundness can be made an arbitrarily large
constant (Theorem 4.2). This result immediately yields a super-constant lower bound on coloring
2-colorable 4-uniform hypergraphs: we prove that c-coloring such hypergraphs is NP-hard for
any constant c (Theorem 4.4), and moreover there exists a constant c 0 > 0 such that, unless
NP  DTIME(n O(log log n) ), there is no polynomial time algorithm to color a 2-colorable 4-uniform
hypergraph using c 0
log log n
log log log n colors (Theorem 4.6). A similar hardness result also holds for coloring
2-colorable k-uniform hypergraphs for any k  5 by reduction from the case of 4-uniform
hypergraphs (Theorem 4.7). Prior to our work, no non-trivial inapproximability results seem to be
known for coloring 2-colorable hypergraphs, and in fact it was not known if 3-coloring a 2-colorable
4-uniform hypergraph is NP-hard.
We note that we do not have analogous results for the hardness of coloring 2-colorable 3-uniform
hypergraphs. The di-culty in capturing the problem stems from the di-culty of analyzing the
underlying maximization problem. The natural maximization version of hypergraph 2-coloring is
the following: color the vertices with two colors so that a maximum number of hyperedges are non-
monochromatic. For l-uniform hypergraphs, this is problem is known as Max l-Set Splitting. For
case we study here), a tight hardness result of 7=8 known [17] and this fact works
its way into our analysis. For hardness result is not known for the maximization
version (see [14]) and our inability to show hardness results for 3-uniform hypergraphs seems to
stem from this fact.
Organization. In Section 2, we go over some of the denitions more formally and relate covering
complexity to approximability of hypergraph coloring. In Section 3, we analyze a simple cPCP
verier that makes 4 queries and has perfect completeness and o(1) soundness. In Section 4, we
analyze a more complicated cPCP verier with similar parameters whose acceptance condition is
not-all-equal-sat. This yields the hardness result for coloring 2-colorable, 4-uniform hypergraphs.
This is the complete version of the conference paper [15].
Preliminaries
In this section we introduce covering PCPs formally, and establish a connection (in the wrong
direction) between covering PCPs and inapproximability of hypergraph coloring.
2.1 Probabilistically checkable proofs (PCPs)
We rst give a formal denition of a PCP. Below veriers are probabilistic oracle Turing machines
whose output, on input x and random string r with oracle O, is denoted V O (x; r). The output is
a bit with 1 denoting acceptance and 0 denoting rejection.
Denition 1 Let c and s be real numbers such that 1  c > s  0. A probabilistic polynomial time
oracle Turing machine V is a PCP verier with soundness s and completeness c for a language L
For x 2 L there exists oracle  such that Prob r [V  (x;
For x 62 L, for all
Two parameters of interest in a PCP are the number of random bits used by the verier and
the number of queries it makes to the proof oracle. Most of the time the symbols of  are bits and
whenever this is not the case, this is stated explicitly.
Denition 2 For functions restricted if, on any input of
length n, it uses at most r(n) random bits and makes at most q(n) queries to .
We can now dene classes of languages based on PCPs.
Denition 3 (PCP) A language L belongs to the class PCP c;s [r; q] if there is an (r; q)-restricted
verier V for L with completeness c and soundness s.
Next we have the denition of covering PCP.
Denition 4 (Covering PCP) A language L belongs to the class cPCP c;s [r; q] if there is an
q)-restricted verier V such that on input x:
(i) if x 2 L then there is a set of proofs f 1=c such that for every random
string r there exists a proof  i such
L, then for every set of k proofs f with k < 1=s, there is a random
string r for which V rejects every  i , 1  i  k.
One usually requires \perfect completeness" seeking PCP characterizations. It
is clear from the above denitions that PCP 1;s [r; q]  cPCP 1;s [r; q] and thus obtaining a PCP
characterization for a language class is at least as hard as obtaining a covering PCP characterization
with similar parameters.
2.2 Covering PCPs and Graph Coloring
We now verify our intuition that \good" covering PCPs (i.e., those which have a large gap in
covering complexity between the completeness and soundness cases) are necessary for strong lower
bounds on the approximating the chromatic number. As usual, for a graph G, we denote by (G)
its chromatic number, i.e., the minimum number of colors required in a proper coloring of G.
Below, we use the phrase \it is NP-hard to distinguish f(n)-colorable graphs from g(n)-colorable
graphs" to mean that \the (2; f; g)-approximation problem is NP-hard". As mentioned in Section 1,
note that we are using a conservative denition of NP-hardness and hence this statement implies
that there is a many-one reduction from SAT that maps satisable instances of SAT to f(n)
colorable graphs and maps unsatisable instances to graphs that are not g(n)-colorable. Under
this assumption, we show how to get nice covering PCPs. Below and throughout this paper, the
function log denotes logarithms to base two.
Proposition 2.1 Suppose for functions f; given a graph G on n vertices, it is
NP-hard to distinguish between the cases (G)  f(n) and (G)  g(n). Then
Proof: Let the vertex set of G be g. The covering PCP consists of proofs
that correspond to \cuts" G, i.e., each  i is n-bits long, with the j th
bit being 1 or 0 depending on which side of the cut i contains v j . The verier simply picks two
vertices
and
at random such that they are adjacent in G, and then check if the j th
1 and j thbits dier in any of the k proofs. The minimum number k of proofs required to satisfy the verier
for all its random choices is clearly the cut cover number (G) of G, i.e., the minimum number of
cuts that cover all edges of G. It is easy to see that (G)e, and therefore the claimed
result follows. 2
One can get a similar result for any base q, by letting the proofs be q-ary strings and the verier
read two q-ary symbols from the proof. In light of this, we get the following.
Corollary 2.2 Suppose that there exists an " > 0 such that it is NP-hard, given an input graph
G, to distinguish between the cases when G is 3-colorable and when (G)
cPCP 1;(" log 3 n) 1 [O(log n); 2] where the covering PCP is over a ternary alphabet, and the verier's
action is to simply read two ternary symbols from the proof and check that they are not equal.
In light of the above Corollary, very powerful covering PCP characterizations of NP are necessary
in order to get strong hardness results for coloring graphs with small chromatic number. A result
similar to Proposition 2.1, with an identical proof, also holds for hypergraph coloring, and thus
motivates us to look for good covering PCP characterizations of NP in order to prove hardness
results for coloring 2-colorable hypergraphs.
Proposition 2.3 Suppose that there exists a function f given an input
r-uniform hypergraph on n vertices, it is NP-hard to distinguish between the cases when it is 2-
colorable and when it is not f(n)-colorable. Then, NP  cPCP
log f(n)
[O(log n); r]. In particu-
lar, if c-coloring 2-colorable r-uniform hypergraphs is NP-hard for every constant c, then NP
[O(log n); r] for every constant k  1.
3 PCP Construction I
We now move on to the constructions of our proof systems. To a reader familiar with PCPs we
rst give a preview of our constructions. Both our PCPs (of this section and the next) go through
the standard path. We start with strong 2-prover 1-round proof systems of Raz [28], apply the
composition paradigm [5], and then use the long code of [8] at the bottom level. One warning: in
the literature it is common to use a variant of the long code | called the \folded long code" | we
do not use the folded version. (Readers unfamiliar with the terms above may nd elaborations in
Section 3.1.)
As usual, the interesting aspects in the constructions are choice of the inner veriers and the
analyses of their soundness. The inner veriers that we use are essentially from [17]: The inner
verier in Section 4 is exactly the same as the one used by [17, Section 7] to show hardness of
Max 4-Set Splitting, while the one in this section is a small variant. The goals of the analyses
are dierent, since we are interested in the number of proofs required to cover all random strings.
Despite the dierence, we borrow large parts of our analysis from that of [17]. In the current section
our analysis essentially shows that if our verier, on some xed input, rejects every proof oracle
with probability at least
, then on any set of k proofs nearly
k fraction of random strings end up
rejecting all the proofs. Thus the standard soundness of the verier we construct is of interest and
we analyze this using lemmas from [17]. The analysis of the verier in Section 4 does involve some
new components and we will comment upon these in the next section.
3.1 Preliminaries: Label cover, Long codes, Proof composition
Our PCP constructions (also) follow the paradigm of proof composition, by composing an \outer
verier" with an \inner verier". In its most modern and easy to apply form, one starts with
an outer proof system which is a 2-Prover 1-Round proof system (2P1R) construction for NP. We
abstract the 2P1R by a graph-theoretic optimization problem called Label Cover. The specic
version of Label Cover we refer to is the maximization version LabelCover max discussed in [3]
(see [3] for related versions and the history of this problem).
Label Cover. A LabelCover max instance LC consists of a bipartite graph
vertex set U [ W and edge set F , \label sets" LU ; LW which represent the possible labels that
can be given to vertices in U; W respectively, and projection functions  for each
W such that (u; w) 2 F . The optimization problem we consider is to assign a
label '(u) 2 LU (resp. '(w) 2 LW ) to each u 2 U (resp. w 2 W ) such that the fraction of edges
(call such an edge \satised") is maximized. The optimum
value of a LabelCover max instance LC, denoted OPT(LC), is the maximum fraction of \satised"
edges in any label assignment. In the language of LabelCover max , the PCP theorem [5, 4] together
with the parallel repetition theorem of Raz [28] yields parts (i)-(iii) of the theorem below. Here we
need an additional property that is also used in [17, Sections 6, 7]. First we need a denition: For
min
The denition above is quite technical (and borrowed directly from [17]) but the intuition is that
projects mostly onto dierent elements of LU i the \measure"  is large.
Theorem 3.1 ([3, 17]) There exist d 0 ; e 0 < 1 and c > 0 and a transformation that, given a
parameter - > 0, maps instances ' of Sat to instances
of LabelCover max , in time n O(log - 1 ) , such that
where n is the size of the Sat instance '.
(iii) If ' is satisable then ' is not satisable then OPT(LC)  -.
(iv) For every
Fg.
Remark: As mentioned earlier, conditions (i)-(iii) are standard for LabelCover max . The need for
Condition (iv) is inherited from some lemmas of [17] that we use (specically, Lemmas 3.3 and 3.4).
This condition is shown in Lemma 6.9 of [17].
To use the hardness of label cover, we use the standard paradigm of proof composition. The
use of this paradigm requires an error-correcting code, which in our case is again the long code.
We dene this next.
The Long Code. We rst remark on some conventions and notation we follow through the rest
of this paper: We represent Boolean values by the set f1; 1g with 1 standing for False and 1
for True. This representation has the nice feature that Xor just becomes multiplication. For any
domain D, denote by FD the space of all Boolean functions f 1g. For any set D, jDj
denotes its cardinality.
We now describe a very redundant error-correcting code, called the long code. The long code
was rst used by [8], and has been very useful in most PCP constructions since.
The long code of an element x in a domain D, denoted LONG(x), is simply the evaluations of
all the 2 jDj Boolean functions in FD at x. If A is the long code of a, then we denote by A(f) the
coordinate of A corresponding to function f , so that
We note that most of the proofs used in the literature use the \folded long code" which is a
code of half the length of the long code, involving evaluations of the elements x at exactly one of
the functions f or f (but not both). For reasons that will become clearer later, we cannot use
the folded long code here and work with the actual long code.
Constructing a \Composed" PCP. Note that Theorem 3.1 implies a PCP where the proof
is simply the labels of all vertices in U; W of the LabelCover max instance and the verier picks
an edge at random and checks if the labels of u and w are \consistent", i.e.,
u;w An alternative is to choose a random neighbor w 0 of u and instead checking
u;w dening '(u) to be the most common value of  u;w 0 ('(w 0 )) it is easy
to see that the probability of acceptance in the latter PCP (that uses w; w 0 for the check) is at
most the probability of acceptance in the former PCP (that uses u; w for the check).
By the properties guaranteed in Theorem 3.1, either PCP uses O(log n log - 1 ) randomness, has
perfect completeness and soundness at most -. While the soundness is excellent, the number of bits
it reads from the proof in total (from the two \locations" it queries) is large (namely, O(log - 1 )).
In order to improve the query complexity, one \composes" this \outer" verication with an \inner"
verication procedure. The inner verier is given as input a projection function
has oracle access to purported encodings, via the encoding function Enc of some error-correcting
code, of two labels a 2 LU and b 2 LW , and its aim is to check that (b) = a (with \good"
accuracy) by making very few queries to Enc(a) and Enc(b). The inner veriers we use have a
slightly dierent character: they are given input two projections  1 and  2 (specically  u;w and
u;w 0 ) and have oracle access to purported encodings Enc(b) and Enc(c) of two labels b; c 2 LW ,
and the aim is to test whether  1 This interesting feature was part of and necessary
for Hastad's construction for set splitting [17], and our PCPs also inherit this feature.
In our nal PCP system, the proof is expected to be the encodings of the labels '(w) of all
vertices using the encoding Enc. For e-cient constructions the code used is the long code
of [8], i.e., Enc
=LONG. We denote the portion of the (overall) proof that corresponds to w by
LP(w), and in a \correct" proof LP(w) would just be LONG('(w)) (the notation LP stands for \long
proof").
The construction of a PCP now reduces to the construction of a good inner verier that given a
pair of strings B; C which are purportedly long codes, and projection functions  1 and  2 , checks if
these strings are the long codes of two \consistent" strings b and c whose respective projections agree
(i.e., satisfy  1 Given such an inner verier IV, one can get a \composed verier" V comp
using standard techniques as follows (given formula ' the verier rst computes the LabelCover max
instance LC in polynomial time and then proceeds with the verication):
1. Pick u 2 U at random and w; w 0 2 N(u) at random
2. Run the inner verier with input  u;w and  u;w 0 and oracle access to LP(w) and LP(w 0 ).
3. Accept i the inner verier IV accepts
We denote by V comp (IV) the composed verier obtained using inner verier IV. The (usual)
soundness analysis of the composed PCP proceeds by saying that if there is a proof that causes the
verier V comp to accept with large, say (s "), probability, where s is the soundness we are aiming
for, then this proof can be \decoded" into labels for U [ W that \satisfy" more than a fraction -
of the edges in the LabelCover max instance, and by Theorem 3.1 therefore the original formula '
was satisable. In our case, we would like to make a similar argument and say that if at most k
proofs together satisfy all tests of V comp , then these proofs can be \decoded" into labels for U [W
that satisfy more than - fraction of edges of LC.
3.2 The Inner Verier
We now delve into the specication of our rst \inner verier", which we call Basic-IV4. This inner
verier is essentially the same as the one for 4-set splitting in [17], but has a dierent acceptance
predicate. Recall the inner verier is given input two projections functions
has oracle access to two tables and aims to check that B (resp. C) is the
long code of b (resp. c) which satisfy  1
Inner Verifier Basic-IV4 B;C
Choose uniformly at random f 2 FLU ,
Choose at random g 0 ; h 0 2 FLW such that 8b 2 LW ,
For a technical reason, as in [17], the nal inner verier needs to run the above inner verier for
the bias parameter p chosen at random from an appropriate set of values. The specic distribution
we use is the one used by Hastad [17] (the constant c used in its specication is the constant from
Equation (2) in the statement of Theorem 3.1).
Inner Verifier IV4 B;C
e,
t.
Choose uniformly at random.
Run Basic-IV4 B;C
Note that the inner verier above has perfect completeness. Indeed when B; C are long codes
of b; c where  1 then for each f 2 FLU , if
so these are not equal, and similarly for the case when
3.3 Covering Soundness analysis
Let X(
) be the indicator random variable for the rejection of a particular proof
Wg by the composed verier V comp (IV4
)). The probability that V 1 (
rejects
taken over its random choices is clearly the expectation
Here B; C are shorthand for LP(w) and LP(w 0 ) respectively and equal
respectively in a \correct" proof. We wish to say that no k proofs can together satisfy all the tests
which
performs.
) is the indicator random variable for the rejection of a set of k
proofs fLP by the verier V 1 (
), then the overall probability that V 1 (
rejects all these k proofs, taken over its random choices, is exactly
Y
where we use the shorthand
We now argue (see Lemma 3.2 below) that if this rejection probability is much smaller than
there is a way to obtain labels '(u) for
than - fraction of the edges (u; w) are satised by this labeling, i.e., Together
with Theorem 3.1, this implies that the rejection probability (from Equation (4)) for any set of k
proofs for a false claim of satisability (of '), can be made arbitrarily close to 1
, and in particular
is non-zero, and thus the covering soundness of the composed verier is at most 1=k.
Lemma 3.2 There exists a 0 < 1 such that for every integer k  1, every ", 0 < " < 4 k , and all
a 0 Before presenting the formal proof of Lemma 3.2, we rst highlight the basic approach. The
power of arithmetizing the rejection probability for a set of k proofs as in Equation (4) is that one
can expand out the product and analyze the expectation of4 k
where
products are dened to be 1. A special
term is which is the constant 1. We analyze the rest of the terms individually. We
can now imagine two new proofs ~
are exclusive-ors of subsets of the k
given proofs. Now one can apply existing techniques from [17] to analyze terms involving the tables
~
B and ~
C and show that ~
cannot be too negative, and similarly if the
expectation of ~
much below zero, then in fact OPT(LC) is quite large.
In short, at a high level, we are saying that if there exist k proofs such that the verier accepts at
least one of them with good probability, then some exclusive-or of these proofs is also accepted by
the verier with good probability, and we know this cannot happen by the soundness analysis of
[17] for the case of a single proof. This intuition is formalized via the next two lemmas from [17].
Before stating the lemmas, we make a slight digression to point out the relevance of not employing
folding here. Folded long codes are typically used as follows: Given a table
supposedly giving the long code of the encoding of the label assigned to w, conceptually we assume
we have a long proof A which respects the constraints A 0
such an A 0 for ourselves from A 0 by setting A 0
xed element of the concerned domain (i.e., LU or LW as the case
might be). Such a table A 0 , which satises A 0 ( f) = A 0 (f) for every function f , is said to be
folded. We then pretend the verier works with the long code, but carry out the soundness analysis
only for folded tables. In our case also we could do the same to analyze the acceptance of a single
proof. However when faced with multiple proofs, the intermediate tables we consider, such as B S
above, need not be folded even if the original proofs we were given were folded | in particular, this
will be the case when S has even cardinality. Thus our analysis needs to work with non \folded
tables" as well. This is why we work with the long code directly.
Now we go back to the technical lemmas.
Lemma 3.3 ([17]) For every
where the distribution of p; f; 2 is the same as the one in IV4
.
This lemma is Lemma 7.9 in [17] combined with calculation in the rst half of Lemma 7.14
in the same paper. Similarly the next lemma follows from Lemma 7.12 of the same paper and a
similar calculation.
Lemma 3.4 ([17]) There exists a < 1 such that for every
> 0 and all proof tables fBw g and
fCw g, indexed by w 2 W with Bw
is at leastOPT(LC)
where the expectation is taken over and where the distribution of
is the same as the one in IV4
.
We are now ready to prove Lemma 3.2.
Proof of Lemma 3.2: The proof is actually simple given Lemmas 3.3 and 3.4. We pick a
that satises
< ". By Equation (4), if E [X k (
", then there exist subsets S 1
;, such that
Suppose one of S 1 , S 2 is empty, say S applied to B S 1
(which is a function
mapping
which together with Equation (6) above
yields
> ", a contradiction since
"=8.
Now suppose both S 1 and S 2 are non-empty. Now we apply Lemma 3.4 to B S 1
and C S 2
to get
that the expectation in Equation (6) is at least 7
a. Together with Equation
this yields (using "  8
a>
a 0 for some absolute constant a 0 . 2
We are now ready to state and prove the main Theorem of this section.
Theorem 3.5 For every constant k, NP  cPCP
Proof: The theorem follows from Lemma 3.2 and Theorem 3.1. Let
pick - > 0 small enough so that
a 0 > -. By Lemma 3.2 we have
implies OPT(LC) > -. Consider the PCP with verier V comp (IV4
). Using Theorem 3.1, we get
that if the input formula ' is not satisable, the verier V comp (IV4
rejects any k proofs with
probability at least 1
it clearly has perfect completeness and makes only 4 queries, the
claimed result follows. 2
Remark on tightness of the analysis: In fact, Lemma 3.2 can be used to show that for any
" > 0, there exists a (covering) PCP verier that makes 4 queries, has perfect completeness and
which rejects any set of k proofs with probability at least 1
". Note that this analysis is in fact
tight for the verier V comp (IV4) since a random set of k proofs is accepted with probability 1 4 k .
It would have been su-cient to prove that for any k proofs the set of verier coins causing the
verier to reject all k proofs is nonempty. We do not know a simpler proof of this weaker statement.
Construction II and Hardness of Hypergraph Coloring
In the previous section we gave a PCP construction which made only 4 queries into the proof and
had covering soundness smaller than any desired constant. This is already interesting in that it
highlights the power of taking the covering soundness approach (since as remarked in the introduction
one cannot achieve arbitrarily low soundness using classical PCPs with perfect completeness
that make some xed constant number of queries). We next turn to applying this to get a strong
inapproximability result for hypergraph coloring.
The predicate tested by the inner verier IV4
is F (x; w), and to get
a hardness result for hypergraph coloring, we require the predicate to be NAE(x; which is
true unless all of x; are equal. Note that NAE(x;
true, so one natural approach is to simply replace the predicate F tested by IV4
by NAE without
losing perfect completeness. The challenge of course is to prove that the covering soundness does
not suer in this process, and this is exactly what we accomplish. For completeness we describe
the inner verier below.
Inner Verifier IV-NAE4 B;C
Pick p as in IV4
.
Pick f; as in Basic-IV4 p .
Accept i not all of B(g 1 are equal.
To analyze the soundness of the resulting composed verier, we need to understand the \not-
all-equal" predicate NAE. Note that NAE(x; rejects i8
and this sum equals zero otherwise. With similar notation as in the previous section this implies
that for a given choice of the verier rejects all k proofs i
where  denotes the exclusive-or of characteristic vectors, or worded dierently, symmetric dier-
ence of sets. If the verier accepts one the proofs then the right hand side of (7) must equal zero.
Hence we study the expected value of this quantity.
Before proceeding with the analysis we shed some insight into the analysis and explain what
is new this time. Let . The terms corresponding to T being the
empty set are exactly the terms that appeared in the analysis of the verier of Section 3. Let
us turn our attention to terms where T 6= ;. Typically, when a sum as the above appears,
we would just go ahead and analyze the individual terms. Unfortunately, it turns out that
we are unable to do this in our case. To see why, consider a typical summand above, namely
These are more general than the terms analyzed in Section
3, which were of the form B The rst two elements of such a
product come from an identical distribution, and similarly for the last two elements of the product.
This in turn enabled a certain \pairing" up of terms from which a good solution to the label cover
instance could be extracted (see the analysis in Lemma 7.12 of [17] for more details). But now,
since T 6= ;, the rst two tables,
and are dierent, and so are the last two. Therefore,
we now have to deal with individual terms which are the product of four elements each of which
comes from a dierent distribution. It does not seem possible to analyze such a term by itself and
extract meaningful solutions to the label cover instance.
To cope with this problem, we now bunch together terms
that involve the same T but dierent S 1 and S 3 . (Alternatively, one could think of this as xing T ,
and then picking S 1 and S 3 as random subsets of [k] and considering the expectation of the terms
This makes the distribution of the rst pair as a whole identical to that of the
second pair, and allows us to analyze the terms above. More formally, for each non-empty T  [k],
and similarly for C. Using this notation the sum in Equation (7) equals

where the rst four terms correspond to the case where can be used to lower
bound the expectation of the rst two sums over Lemma 3.4 can be used to lower
bound the expectation of the third sum as a function of the optimum of the label cover instance.
Thus we only need to study the last sum.
We show that if the last term is too negative, then one can extract an assignment of labels to
the provers. The intuition behind the proof is as follows. B T and C T are two functions chosen
independently from the same distribution. Further, the queried pairs (g are also
chosen from the same distribution, but are not independent of each other (and are related via f ).
If we ignore this dependence for a moment, then we get:
and this would be good enough for us. Unfortunately, (g are not independent. The
intuition behind the proof of the next inequality is that if this correlation aects the expectation
of then there is some correlation between the tables for B T and C T and
so a reasonable strategy for assigning labels to w and w 0 can be extracted. Specically, we get the
following lemma:
Lemma 4.1 There exists a 0 < 1 such that the following holds: Let T
"=8 be such that
";
where the expectation is taken over the distribution of u; w; w as in IV-NAE4
.
Then OPT(LC)
a 0 As usual we postpone the proof of the lemma, and instead prove the resulting theorem.
Theorem 4.2 For every constant k, NP  cPCP
moreover the predicate veried
by the PCP upon reading bits x;
Proof: We only have to analyze the soundness of the verier. Let a be the constant from
Lemma 3.4 and a 0 be the constant from Lemma 4.1. Let g. Let
and let - <
b. To create a verier for an instance SAT, reduce the instance of SAT to an
instance of Label Cover using Theorem 3.1 with parameter - and then use the verier based on
using IV-NAE4
as the inner verier. To show soundness, we need to show that if this verier is
covered by k proofs, then the instance of Label Cover has an optimum greater than -.
Suppose we have k proofs such that the verier always accept one of the proofs. This implies
that the expectation, over u; w; w of (9) is 0. This implies that at least one
of summands in (9) is less than or equal to 2 (k+2) in expectation (since there are at most
summands in the expression). If it is a summand in one of the rst two sums then this
contradicts Lemma 3.3. If it is a summand in the third sums then by Lemma 3.4, we get that
a> -. If it is a summand in the last sum, then by Lemma 4.1 we get that
a 0 > -. Thus in the last two cases we get that the optimum is more than - as
desired. 2
Before going on to the proof of Lemma 4.1, we discuss the consequences of Theorem 4.2 to
hypergraph coloring. Before doing so, we just note that in fact one can prove a stronger claim in
Theorem 4.2 that given any k proofs, the probability that the verier rejects all of them is at least8 k ", for " > 0 as small as we seek. The proof is really the same as that of Theorem 4.2, since
we have argued that all terms in the expansion (9) are arbitrarily small in the case when optimum
value of the label cover instance is very small. Once again this soundness analysis is tight, since a
random set of k proofs will, in expectation, satisfy a fraction 1 1
8 k of the verier's checks.
4.1 Hardness results for hypergraph coloring
Since the predicate used by the PCP of Theorem 4.2 is that of 4-set splitting, we get the following
Corollary.
Corollary 4.3 For every constant k  2, given an instance of 4-set splitting, it is NP-hard to
distinguish between the case when there is a partition of the universe that splits all the 4-sets, and
when for every set of k partitions there is at least one 4-set which is is not split by any of the k
partitions.
The above hardness can be naturally translated into a hardness result for coloring 4-uniform hy-
pergraphs, and this gives us our main result:
Theorem 4.4 (Main Theorem) For any constant c  2, it is NP-hard to color a 2-colorable
4-uniform hypergraph using c colors.
Proof: Follows from the above Corollary since a 4-set splitting instance can be naturally identied
with a 4-uniform hypergraph whose hyperedges are the 4-sets, and it is easy to see that the minimum
number of partitions k needed to split all 4-sets equals dlog ce where c is the minimum number of
colors to color the hypergraph such that no hyperedge is monochromatic. 2
In light of the discussion after the proof of Theorem 4.2, we in fact have the following stronger
result.
Theorem 4.5 For any constant c  2 and every " > 0, it is NP-hard to color a 2-colorable 4-
uniform hypergraph using c colors such that at least a fraction (1 1
") of the hyperedges are
properly colored (i.e., are not monochromatic).
Theorem 4.6 Assume NP 6 DTIME(n O(log log n) ). Then there exists an absolute constant c 0 > 0
such that there is no polynomial time algorithm that can color a 2-colorable 4-uniform hypergraph
using c 0
log log n
log log log n colors, where n is the number of vertices in the hypergraph.
Proof: This follows since the covering soundness of the PCP in Theorem 4.2 can be made an
explicit o(1) function. Indeed, nothing prevents from having a k that is a function of n. We
need to have
and to reach a contradiction - <
O(
. The proof size we need
is . We can thus have n O(log log n) size proofs by letting

log log n
log log log n ). Similarly to Theorem 4.4, this implies 2 k -coloring a 2-colorable
4-uniform hypergraph is hard unless NP  DTIME(n O(log log n) ). 2
We now show that a hardness result similar to Theorem 4.4 also holds for 2-colorable k-uniform
hypergraphs for any k  5.
Theorem 4.7 Let k  5 be an integer. For any constant '  2, it is NP-hard to color a 2-colorable
k-uniform hypergraph using ' colors.
Proof: The proof works by reducing from the case of 4-uniform hypergraphs, and the claimed
hardness then follows using Theorem 4.4.
Let H be a 4-uniform hypergraph with vertex set V . Suppose that
Construct a k-uniform hypergraph H 0 as follows. The vertex set of H 0 is
where the sets V (j) are independent copies of V . On each V (j) , take a collection F (j) of 4-element
subsets of V (j) that correspond to the hyperedges in H. A hyperedge of H 0 (which is a (4s
element subset of
now given by the union of s 4-sets belonging to s dierent F (j) 's,
together with t vertices picked from a 4-set belonging to yet another F (j) . More formally, for every
set of (s every choice of elements
and every t-element subset f j s+1 of e j s+1 , there is a hyperedge
If H is 2-colorable then clearly any 2-coloring of it induces a 2-coloring of H 0 , and hence H 0 is
2-colorable as well.
Suppose H is not '-colorable and that we are given an '-coloring of H 0 . Since H is not '-
colorable, each F (j) , for 1  j  s' must contain a monochromatic set g j . By the pigeonhole
principle, there must be a color c such that dierent g j 's have color c. The hyperedge of
constructed from those (s + 1) sets is then clearly monochromatic (all its vertices have color c)
and we conclude that H 0 is not '-colorable.
Since the reduction runs in polynomial time when k and ' are constants the proof is complete.4.2 Discrete Fourier transforms
Before going on to the proof of Lemma 4.1 we now introduce a tool that has been crucial in the
analysis on inner veriers. This was hidden so far from the reader but already used in the proofs
of Lemmas 3.3 and 3.4 in [17]. Now we need to introduce them explicitly.
In general we consider functions mapping D to f1; 1g. For   D and f 2 FD , let
x2 f(x). Notice that  fxg is the long code of x. For any function A mapping FD to the reals,
we have the corresponding Fourier coe-cients
f
A(f)  (f)
where   D. We have the Fourier inversion formula given by
A    (f)
and Plancherel's equality that states that
f
In the case when A is a Boolean function the latter sum is clearly 1.
We think of an arbitrary table A as being somewhat close to (or coherent with) the long code
of x if there exists a small set  containing x such that ^
A  is non-negligibly large. Thus, when
viewing the long proofs of w and w 0 , our goal is to show that the LP(w) and LP(w 0 ) have coherence
with the long codes of strings x and y such that  u;w (x) and  u;w 0 (y) are equal.
4.3 Proof of Lemma 4.1
Fix T  [k]. Throughout this section the quantities that we dene depend on T , but we don't
include it as a parameter explicitly.
Recall we need to show that if the expectation, over u; w; w
is too negative (less than "), then we can assign labels to the label cover problem with acceptance
probability more that -. Recall that dened in terms of other random
variables f and g 0 and similarly h 2 in terms of f and h 0 . For brevity, we let X denote the quantity
that X is a random variable depending on all the variables above. We
rst analyze the expectation of X over g 1 and h 1 (for xed choice of u; w; w
we calculate the expectation over f , g 0 and h 0 . In both stages we get exact expressions. Finally
we make some approximations for the expectation over u; w; w 0 . (The careful reader may observe
that we don't take expectations over p | in fact the lemma holds for every choice of p of the inner
verier IV-NAE4
.)
The crux of this proof are the functions B dened as follows: We let
and
Note that for a xed choice of f and g 0 we have
We get a
similar expression for C T and thus we get:
Let us call the above quantity Y .
In what follows, we rely crucially on the properties of the Fourier coe-cients of B  and C  .
F  and ^
G  denote the Fourier coe-cients of B  and C  respectively. From the denitions and
some standard manipulation, we get
Using simple Fourier expansion, we can rewrite the quantity we are analyzing as:
Y
Y
The main property about the Fourier coe-cients of B  and C  is that their L 1 norm is bounded.
Specically, we have:
A
We start by dening the strategy we use to assign labels and prove that if the expectation (of
Y ) is large, then the labels give an assignment to the label cover instance with objective of at least
a 0
Strategy. Given w 2 W , and tables corresponding to LP(w) in k dierent proofs,
compute B S for every S  [k], B  and its Fourier coe-cients. Pick a non-empty set   LW with
F  j and assign as label to w, an element x 2  chosen uniformly at random. With
remaining probability, since
may be less than 2 k , assign no label to w.
Preliminary analysis. We now give a preliminary expression for the success probability of the
strategy. Consider picking u; w, and w 0 (and the associated  1 and  2 ) at random and checking for
the event  1 )). The probability of this event is lower bounded by the probability
that  1 () and  2 ( 0 ) intersect and we assign the elements corresponding to this intersection to w
and w 0 . The probability of these events is at least:
Below we show that this quantity is large if the expectation of Y is too small. We now return to
the expectation of Y .
An exact expression for the expectation of Y . We start with some notation. Fix u; w; w
and  1 and  2 . For x 2 LU and ;  0  LW , let s x
Since the argument of s x is always  and the argument of t x is always  0 , we use the shorthand
s x for s x () and t x for t x ( 0 ). Further for real p and non-negative integers s; t, let (p; s; t) =2
, and let (p; we show that
F
Y
To prove the above it su-ces to show that
Y
Y
Factors corresponding to y and z with dierent projections on LU are independent, and thus the
expectation can be broken down into a product of expectations, one for each x 2 LU . Fix x 2 LU
and consider the term
Y
Y
If (or \false") the rst product equals ( 1) sx and the second equals (1 2p) t x . Similarly,
If the rst product equals (1 2p) sx and the second equals ( 1) t x . The events happen
with probability 1=2 each and thus giving that the expectation above (for xed x) equals2
Taking the product over all x's gives (12).
Inequalities on E [Y ]. For every u, we now show how to lower bound the expectation of Y , over
in terms of a sum involving only 's and  0 that intersect in their projections. This
brings us much closer to the expression derived in our preliminary analysis of the success probability
of our strategy for assigning labels and we lower bound a closely related quantity. Specically we
now use the inequality E
guaranteed by the Lemma statement) to show:
x minf1; ps x g is the quantity dened in Equation (1).
inequality with  p ( 0 ) in the exponent follows by symmetry.)
To prove the above, consider the following expression, which is closely related to the expectation
of Y as given by (12).
Y
x
Y
x
First we note that E
0. (Here we are using the fact that
the tables B T and C T are chosen from the same distribution.) Next we note that the dierence
between Y and Y 1 arises only from terms involving ;  0 such that  1 To verify
this, note that if
for every x, if  1 we get that terms corresponding to such pairs of ;  0 vanish in
We conclude:
Y
x
Y
x
Using
taking absolute values we get,
Y
x
Y
x
Y
x
Y
x
where the last inequality uses j(p; t)j  1 for every t  0.
Next we simplify the terms of the LHS above. First we show that for every t  0,
First we note both j(p; s; t)j and j(p; s)j are upper bounded by 1
If p  s 1 , then we have 1
s , let us set
To show (15), we need to prove that (z)  0 for z 2 [0; 1]. We have
in the interval in question and we only have to check
the inequality at the end points. We have
Using (15) we conclude that
Y
x
Y
x
Y
x
Substituting the above into (14) gives (13).
Based on (13). we want to prove that the strategy for assigning labels is a good one. First we
prove that large sets  do not contribute much to the LHS of the sum in (13). Dene
We have
Lemma 4.8 We have
"=4:
Proof: By Property (iv) of Theorem 3.1 we have that the probability that  p ()  (4k
is at most "2 (2k+4) . A similar chain of inequalities as (10) shows that
The sum in the lemma can hence be estimated as
"=4;
and the lemma follows. 2
By the same argument applied to  0 of size at least K, together with Equation (13), we get
"=2: (16)
We now relate to the probability of success of our strategy for assigning labels. From (11) we know
this quantity is at least
"2 (2k+2)
where the last inequality uses (16). (It is easy to convert this randomized strategy for assigning
labels to a deterministic one that does equally well.) The dominating factor in the expression is
the term p O(1) (from the denition of K) which can be calculated to be
O(
and the proof of
Lemma 4.1 is complete. 2
4.3.1 Comparison to previous proof of Theorem 4.4
We point out that the conference version of this paper [15] contained a dierent proof of Theorem
4.4. The current proof is signicantly simpler, and furthermore it is only a minor adjustment
of similar proofs in [17]. The key observation to make the current proof possible is the insight that
we should treat the terms of (7) in the collections given by B T (g does not
seem possible to handle them one by one in an e-cient manner. The previous proof did not make
this observation explicitly and ended up being signicantly more complicated. This \simplicity" in
turn has already enabled some further progress on the hypergraph coloring problem | in partic-
ular, using this style of analysis, Khot [21] shows a better super-constant hardness for a-colorable
4-uniform hypergraphs for a  7.
4.3.2 Subsequent related work
In a very recent work, Holmerin [18] showed that the vertex cover problem considered on 4-uniform
hypergraphs is NP-hard to approximate within a factor of (2 ") for arbitrary " > 0.
of vertices of a hypergraph H is said to be a vertex cover if every hyperedge of H intersects S.) He
proves this by modifying the soundness analysis of Hastad's 4-set splitting verier (which is also the
verier we use in Section 4) to show that any proof which sets only a fraction " of bits to 1 will
cause some 4-tuple tested by the verier to consist of only 1's. This in turn shows that for every
constant " > 0, given a 2-colorable 4-uniform hypergraph, it is NP-hard to nd an independent set
that consists of a fraction " of vertices. Note that this result is stronger as a small independent
set implies a large chromatic number and it thus immediately implies the hardness of coloring such
a 2-colorable 4-uniform hypergraph with 1=" colors, and hence our main result (Theorem 4.4).
We stress that the verier in Holmerin's paper is the same as the one in this paper; however, the
analysis in [18] obtains our result without directly referring to covering complexity.

Acknowledgments

We would like to thank the anonymous referees and Oded Goldreich for useful comments on the
presentation of the paper.



--R

Coloring 2-colorable hypergraphs with a sublinear number of colors
The hardness of approximate optima in lattices
Hardness of Approximations.
Proof veri
Probabilistic checking of proofs: A new characterization of NP.

An algorithmic approach to the Lov
Free bits
Improved approximation for graph coloring.
Coloring bipartite hypergraphs.


Improved approximation algorithms for maximum cut and satis
Inapproximability results for set splitting and satis

On the hardness of 4-coloring a 3-colorable graph

Vertex cover on 4-regular hyper-graphs is hard to approximate within (2 ")
Approximate graph coloring using semide
On the hardness of approximating the chromatic number.
Hardness results for approximate hypergraph coloring.
Approximate coloring of uniform hypergraphs.

On the hardness of approximating minimization problems.
A random recoloring method for graphs and hypergraphs.
Hypergraph coloring and the Lov
Improved bounds and algorithms for hypergraph 2- coloring
A parallel repetition theorem.
Coloring n-sets red and blue
--TR

--CTR
Adi Avidor , Ricky Rosen, A note on unique games, Information Processing Letters, v.99 n.3, p.87-91, August 2006
Subhash Khot, Guest column: inapproximability results via Long Code based PCPs, ACM SIGACT News, v.36 n.2, June 2005
covering PCP;set splitting;hypergraph coloring;hardness of approximations;PCP;graph coloring