Authors David Zuckerman,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128
http://theoryofcomputing.org
Linear Degree Extractors and the
Inapproximability of Max Clique and
Chromatic Number
David Zuckerman∗
Received: November 7, 2006; revised: July 19, 2007; published: August 6, 2007.
Abstract: We derandomize results of Håstad (1999) and Feige and Kilian (1998) and show
that for all ε > 0, approximating M AX C LIQUE and C HROMATIC N UMBER to within n1−ε
are NP-hard. We further derandomize results of Khot (FOCS ’01) and show that for some
γ > 0, no quasi-polynomial time algorithm approximates M AX C LIQUE or C HROMATIC
1−γ
N UMBER to within n/2(log n) , unless NP̃ = P̃.
The key to these results is a new construction of dispersers, which are related to random-
ness extractors. A randomness extractor is an algorithm which extracts randomness from
a low-quality random source, using some additional truly random bits. We construct new
extractors which require only log2 n + O(1) additional random bits for sources with con-
stant entropy rate, and have constant error. Our dispersers use an arbitrarily small constant
∗ Most of this work was done while visiting Harvard University, and was supported in part by a Radcliffe Institute for
Advanced Study Fellowship, a John Simon Guggenheim Memorial Foundation Fellowship, a David and Lucile Packard Fel-
lowship for Science and Engineering, and NSF Grants CCR-0310960 and CCF-0634811. A preliminary version of this paper
appeared in STOC’06.
ACM Classification: F.2, G.3, G.2
AMS Classification: 68Q17, 68R10, 65C10
Key words and phrases: extractor, disperser, clique, chromatic number, approximation, pseudorandom,
explicit construction, NP-hard
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2007 David Zuckerman DOI: 10.4086/toc.2007.v003a006
D. Z UCKERMAN
times log n additional random bits for sources with constant entropy rate. Our extractors
and dispersers output 1 − α fraction of the randomness, for any α > 0.
Our constructions rely on recent results in additive number theory and extractors by
Bourgain, Katz, and Tao (2004), Barak, Impagliazzo, and Wigderson (FOCS ’04), Barak
et al. (STOC ’05), and Raz (STOC ’05). We also simplify and slightly strengthen key
theorems in the second and third of these papers, and strengthen a related theorem by
Bourgain (2005).
1 Introduction
This work has two sources of motivation: inapproximability and randomness extractors. We begin with
inapproximability.
1.1 Inapproximability
M AX C LIQUE and C HROMATIC N UMBER are central optimization problems. Their decision versions
were in Karp’s original list of NP-complete problems [32]. The best approximation algorithms for
these problems give approximation ratios of the form n/ polylog(n) [8, 24], which is not much better
than the trivial approximation of n. Yet no strong inapproximability results were known until Feige et
al. [18] discovered a connection between probabilistically checkable proofs (PCPs) and M AX C LIQUE.
The celebrated PCP Theorem of Arora et al. [3] then implied that it is NP-hard to approximate M AX
C LIQUE to within nc for some constant c > 0. This ratio was improved in [7, 6] until Håstad, in a
breakthrough, showed a hardness ratio of n1−ε , for any ε > 0 [25]. The catch is that Håstad’s reduction
is randomized, so his theorem assumes that NP 6= ZPP. Assuming only NP 6= P, Håstad’s hardness ratio
becomes n1/2−ε . In this paper we derandomize Håstad’s randomized reduction:
Theorem 1.1. For all ε > 0, it is NP-hard to approximate M AX C LIQUE to within n1−ε .
The inapproximability of C HROMATIC N UMBER has historically been even harder to prove than
M AX C LIQUE, because advances have typically occurred through reductions from M AX C LIQUE. Lund
and Yannakakis were the first to show that it is NP-hard to approximate C HROMATIC N UMBER to within
nc for some constant c > 0 [37]. Other reductions ensued, culminating in Feige and Kilian’s proof of
a hardness ratio of n1−ε [19]. This uses Håstad’s result, so it assumes that NP 6= ZPP. Assuming only
NP 6= P, the best previous hardness ratio explicitly stated appears to be n1/7−ε [6]. Previous work likely
implied something better, though certainly no better than n1/2−ε . In this paper we derandomize Feige
and Kilian’s result:
Theorem 1.2. For all ε > 0, it is NP-hard to approximate C HROMATIC N UMBER to within n1−ε .
Engebretsen and Holmerin [16] improved the hardness ratios for both problems to n1−o(1) under the
stronger assumption that NP 6⊆ ZPTIME(2polylog(n) ). Khot [34] later improved these n1−o(1) factors to
1−γ
n/2(log n) for some constant γ > 0, under the same assumption. We derandomize Khot’s results and
show NP̃-hardness with respect to quasi-polynomial time reductions. Because of the quasi-polynomial
time reductions, NP̃-hardness is weaker than NP-hardness; see Subsection 2.1 for more details.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 104
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
1−γ
Theorem 1.3. For some γ > 0, it is NP̃-hard to approximate M AX C LIQUE to within n/2(log n) .
Theorem 1.4. For some γ > 0, it is NP̃-hard to approximate C HROMATIC N UMBER to within
1−γ
n/2(log n) .
The key to our inapproximability results is constructing an appropriate disperser, which is related
to a randomness extractor. Good dispersers were known to help derandomize inapproximability results
for M AX C LIQUE (e.g., [54, 48]), but it was not known for C HROMATIC N UMBER. Before discussing
dispersers, we discuss extractors.
1.2 Randomness extractors
Randomness extractors are motivated by the possibility of using defective sources of randomness. The
model for defective random source involves lower bounding the min-entropy:
Definition 1.5. The min-entropy of a distribution X is H∞ (X) = minx {− log2 Pr[X = x]}. A k-source is a
distribution with min-entropy at least k. The entropy rate of a k-source on {0, 1}n is k/n; we sometimes
call a k-source a rate-k/n-source.
A randomness extractor is a function which extracts randomness from a k-source using a few addi-
tional uniformly random bits.
Definition 1.6 ([42]). Let U` denote the uniform distribution on ` bits. A function Ext : {0, 1}n ×
{0, 1}d → {0, 1}m is a (k, ε)-extractor if for every k-source X, the distribution Ext(X,Ud ) is ε-close in
statistical (variation) distance to Um . We say Ext is a strong (k, ε)-extractor if the function Ext(x, y) ◦ y
is a (k, ε)-extractor, where ◦ denotes concatenation.
Besides their straightforward applications to simulating randomized algorithms using weak sources,
extractors have had applications to many areas in derandomization that are seemingly unrelated to weak
sources, including inapproximability [54, 51, 40]. Nisan and Ta-Shma [41] survey these applications.
Like many objects in the study of pseudorandomness, the existence of excellent extractors is rel-
atively easy to establish via the probabilistic method. However, the explicit construction of efficient
extractors has proved to be much more difficult.
We wish to construct extractors for any min-entropy k with d, the number of truly random bits, as
small as possible and m, the number of output bits, as large as possible. Different parameter settings
are needed for different applications. Constructing good extractors is highly non-trivial, because such
constructions beat the “eigenvalue bound” [53]. Starting with the first extractor of Nisan and Zucker-
man [42], a lot of effort has been expended constructing good extractors. See Shaltiel’s survey [46] for
more details.
In many applications, extractors are viewed as highly unbalanced strong expanders. In this view an
extractor is a bipartite graph G = (V,W, E) with V = {0, 1}n , W = {0, 1}m , and (x, z) is an edge iff there
is some y ∈ {0, 1}d such that Ext(x, y) = z. Thus, the degree of each vertex of V is D = 2d , and the
extractor hashes the input x ∈ V to a random neighbor among its D neighbors in W .
Often this degree D is of more interest than d = log D. For example, in the samplers of [55] the
degree is the number of samples; in the extractor codes of [48] D is the length of the code; in the
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 105
D. Z UCKERMAN
simulation of BPP using weak sources [54] the degree is the number of calls to the BPP algorithm. Most
relevant for us, in the inapproximability of M AX C LIQUE [54] the size of the graph is closely related
to D.
Before the work of Ta-Shma et al. [49], all explicit extractors had degree D at least some unspecified
polynomial in n = log |V |. In contrast, a non-explicit construction achieves D = O(n) = O(log |V |),
which matches the lower bound. Ta-Shma et al. were able to achieve degree D = O(n log∗ n) for k ≥
√ √
n log2 n, but could only output about k/ n bits. In the case where k = Ω(n), they could output m =
Ω(k) bits, but then they achieved degree D = n · polylog(n). Our new construction achieves linear degree
and linear output length for constant-rate sources.
Theorem 1.7. For all constant α, δ , ε > 0 there is an efficient family of strong (k = δ n, ε)-extractors
Ext : {0, 1}n × {0, 1}d → {0, 1}m with m ≥ (1 − α)δ n and D = 2d = O(n).
We now define the related notion of a disperser. While dispersers are usually defined with respect to
an error parameter ε, here it is more convenient to use the parameter s = 1 − ε.
Definition 1.8. We may view a function DIS : [N] × [D] → [M] as a bipartite graph ([N], [M], E) where
(x, z) ∈ E iff DIS(x, y) = z for some y ∈ [D]. For a set X ⊆ [N], let Γ(X) = {DIS(x, y) | x ∈ X, y ∈ [D]} be
the set of neighbors of X. We say DIS is a (K, s)-disperser if, for any X ⊆ [N] with |X| ≥ K, |Γ(X)| ≥ sM.
We say DIS is a strong (K, s)-disperser if the function DIS(x, y) ◦ y is a (K, s)-disperser, where ◦ denotes
concatenation.
When s is very small (so the error is close to 1), the probabilistic method can be used to show
that there exists dispersers with degree even smaller than n, namely O(n/ log s−1 ). In this paper, we
succeed in matching this degree explicitly for constant-rate sources. These dispersers are the key for our
inapproximability results.
Theorem 1.9. For all constant α, δ > 0 and s = s(n) > 0, there is an efficient family of strong (K =
N δ , s)-dispersers DIS : [N = 2n ] × [D] → [M = 2m ] such that D = O(n/ log s−1 ) and m ≥ (1 − α)δ n. For
subconstant δ = δ (n), the dependence is D = (1/δ )O(1) n/ log s−1 and m = δ O(1) n.
1.3 Techniques
Our techniques are based on a combination of random walks on expanders and additive number theory.
Random walks on expanders have been used to amplify the success probability of RP and BPP algo-
rithms without using many additional random bits [1, 29, 13]. This yields a disperser for sources with en-
tropy rate greater than 1/2 [13]. By using Chernoff bounds for random walks on expanders [21, 31, 52],
we can construct extractors in a similar way. However, random walks provably fail when the entropy
rate drops below 1/2, so they were not considered relevant for this case.
We handle entropy rates below 1/2 by first condensing the input until its entropy rate exceeds 1/2, and
then applying a random walk on an expander. Condensers have been used before to build extractors [44,
47]. We condense using techniques developed from additive number theory.
Our basic condenser requires only one additional random bit, and is very simple. Choose a prime p
and form the line-point incidence graph over Fq , where q = 2 p . This bipartite graph has as independent
sets the lines and points in the plane F2q , with an edge between a point and a line if the point lies on
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 106
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
the line. View the input distribution as a distribution over the q3 edges. On input an edge, use the one
random bit to output a random choice of its two endpoints. If the input distribution has min-entropy
rate δ , then roughly speaking one of the two outputs will have min-entropy rate δ 0 > δ . The proof of
correctness is simple, given the line-point incidence theorem from Bourgain-Katz-Tao [11].
This basic condenser improves that of Barak et al. [5], which requires two random bits. The im-
provement is not necessary for our results, as we apply the basic condenser iteratively to achieve entropy
rate .9. In fact, we use Raz’s condenser [43], which is strong in the sense that with high probability over
the constant-bit seed, the min-entropy rate will increase. We iteratively apply the Raz condenser in a
manner similar to [53], to improve the output length to 1 − α fraction of the input min-entropy, for any
α > 0.
Although not needed for our other results, we further simplify and slightly strengthen other appli-
cations of additive number theory. These applications are based on the important theorem of Bourgain-
Katz-Tao [11] and extended by Bourgain-Glibichuk-Konyagin [10]: in a field Fq where q is either prime
or 2 p for p prime, if |A| ≤ p.9 , then max(|A + A|, |A · A|) ≥ |A|1+α for a global constant α > 0. (See
Section 2.8 for more details, including the recent extension to non-prime fields.) Barak-Impagliazzo-
Wigderson [4] used these ideas to show that for δ ≤ .9, if A, B, and C are independent rate-δ -sources
taking values in Fq , then AB +C is close to a rate-(1 + α 0 )δ -source. We show that A and C do not have to
be independent. Instead, the lemma follows if (A,C) is independent from B. Our overall proof is simpler
than that in [4]. We further strengthen a theorem of Bourgain [9] and show that the function A(A + B)
also gives a rate improvement.
This paper is organized as follows. After some preliminaries in Section 2, we give our basic dis-
perser and extractor constructions in Sections 3 and 4, respectively. We next show how to improve the
output length of both constructions in Section 5. We then give the inapproximability of Max Clique and
Chromatic Number in Sections 6 and 7, respectively. Finally, we improve the additive number theory
applications in Section 8.
2 Preliminaries
Some common notation we use is ◦ for concatenation and [n] for the set {1, 2, . . . , n}. All logarithms are
to the base 2.
When letters denote integers we often use a capital letter to denote 2 to the corresponding small letter,
e.g., K = 2k . When letters denote random variables we often use capital letters for random variables and
corresponding small letters for their instantiations.
For readability, we often assume various quantities are integers when they are not necessarily. It is
not hard to see that this does not affect our analysis.
We often use the term efficient to denote polynomial-time computable.
2.1 Reductions and quasi-NP-hardness
Our NP-hardness results are with respect to polynomial-time, many-one reductions.
Quasi-polynomial in n means 2polylog(n) . NP̃ and P̃ are the quasi-polynomial analogues of NP and P,
respectively. As usual with inapproximability results, we analyze the appropriate gap problem.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 107
D. Z UCKERMAN
Note that no language is NP̃-complete with respect to polynomial-time reductions. For if there were
c c+1
such a language, it would be in TIME(2(log n) ) for some c; but then NP̃ ⊆ TIME(2(log n) ), contradicting
the time hierarchy theorem.
Therefore, we consider NP̃-hardness with respect to quasi-polynomial-time, many-one reductions.
Then any NP-hard language is also NP̃-hard. Moreover, if an NP̃-hard language is in P̃, then NP̃ = P̃.
Of course, NP̃ = P̃ ⇐⇒ NP ⊆ P̃.
2.2 Distance between distributions
For a probability distribution X, X(s) denotes Pr[X = s]. For a set S, X(S) denotes Pr[X ∈ S].
Definition 2.1. Let X1 and X2 be two distributions on the same space Ω. The statistical, or variation,
distance between them is
1
kX1 − X2 k = max |X1 (S) − X2 (S)| =
S⊆Ω
∑ |X1 (s) − X2 (s)| .
2 s∈Ω
We say X1 and X2 are ε-close if kX1 − X2 k ≤ ε, and are ε-far otherwise. We say a distribution on
{0, 1}n is ε-uniform if it is ε-close to Un , the uniform distribution on n bits.
A useful method of computing the distance to the closest k-source is the following.
Lemma 2.2. The distance of X to the closest `-source is ∑s max(X(s) − 2−` , 0).
Of course, only those s with X(s) > 2−` contribute to the above sum.
2.3 Flat sources
Definition 2.3. A source is a probability distribution. A flat source is a source which is uniform on its
support. The support of a distribution X is denoted supp(X).
The following lemma shows that it suffices to consider flat k-sources.
Lemma 2.4 ([12]). Any k-source is a convex combination of flat k-sources.
2.4 Dispersers
Dispersers were defined in Definition 1.8. There are two possible notions of efficiency: one relative to
the input size log N + log D and the other relative to the graph size N + M. For the inapproximability
results, we only need the second, weaker, notion.
Definition 2.5. We say DIS : [N] × [D] → [M] is efficient if it runs in polynomial time in its input size
log N + log D. We say DIS is polynomial-time constructible if the disperser graph is constructible in
polynomial time in the number of vertices N + M.
Of course, efficient implies polynomial-time constructible.
The following simple lemma is useful when D = O(1).
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 108
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
Lemma 2.6. A (K, s)-disperser is also a strong (K, s/D)-disperser.
We also use the following simple lemma.
Lemma 2.7. Given an efficient (K, s0 )-disperser DIS1 : [N] × [D1 ] → [N 0 ] and an efficient (K 0 = s0 N 0 , s)-
disperser DIS2 : [N 0 ] × [D2 ] → [M], we can build an efficient (K, s)-disperser DIS : [N] × [D1 D2 ] → [M].
If moreover DIS2 is a strong (K 0 , s)-disperser, then DIS is a strong (K, s/D1 )-disperser.
Proof. Take DIS(x, y1 ◦ y2 ) = DIS2 (DIS1 (x, y1 ), y2 ). It is straightforward to verify that DIS is a (K, s)-
disperser. To see the final statement of the lemma, suppose DIS2 is strong. Then DIS(x, y1 ◦ y2 ) ◦ y2 is a
(K, s)-disperser, so DIS(x, y1 ◦ y2 ) ◦ y1 ◦ y2 is a (K, s/D1 )-disperser.
While we need the notion of strong disperser for the inapproximability of Chromatic Number, the
notion that suffices for this is captured in the following simple lemma.
Lemma 2.8. Let DIS : [N] × [D] → [M] be a strong (K, s)-disperser. For a set X ⊆ [N], let Γy (X) =
{DIS(x, y) | x ∈ X}. Then DIS has the property that for any X ⊆ [N] with |X| ≥ K, there is a y such that
|Γy (X)| ≥ sM.
2.5 Expander graphs
Expander graphs are related to dispersers, and we use random walks on expanders to build our dispersers.
We define expansion via eigenvalues. Let G be a connected regular undirected graph, and let A be the
transition matrix of a random walk on G. (If M is the adjacency matrix and d the degree, then A = M/d.)
We call G a λ -expander if all eigenvalues of A other than 1 are at most λ in absolute value. Smaller λ
mean better expansion. We will need 2c -regular 2−γc -expanders on 2m nodes, for a constant γ > 0.
Extending earlier constructions which required large primes [36, 38], Morgenstern [39] gave ex-
plicit constructions which achieve this with γ approaching 1/2. However, because the number of ver-
tices is not 2m and there are restrictions on the degree, it is easier to use expanders by Gabber and
Galil [20]. m
√ They gave an explicit construction of 8-regular λ -expanders on 2 nodes, for even m, where
λ = 5 2/8 < 1. (See the survey [28] for the statement in this form, and for many other aspects about
expanders.) The neighbors of a vertex may be computed with a constant number of arithmetic opera-
tions. By taking the (c/3)th power of the graph, we get a 2c -regular λ c/3 -expander, as we need (though
this requires that 3|c).
2.6 Somewhere-random sources
The concept of somewhere-random sources will be useful in constructing dispersers.
Definition 2.9. An elementary somewhere-k-source is a vector of sources (X1 , . . . , X` ), such that some
Xi is a k-source. A somewhere-k-source is a convex combination of elementary somewhere-k-sources.
Note that there may be arbitrary dependencies among the Xi . Further note that in a somewhere-k-
source which is not elementary, all Xi may have low min-entropy.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 109
D. Z UCKERMAN
2.7 Condensers
Condensers and somewhere condensers will be essential in our extractor and disperser constructions,
respectively.
Definition 2.10. A function C : {0, 1}n × {0, 1}d → {0, 1}m is a (k → `, ε)-condenser if for every k-
source X, C(X,Ud ) is ε-close to some `-source. When convenient, we call C a rate-(k/n → `/m, ε)-
condenser. The condenser is strong if the average over y ∈ {0, 1}d of the minimum distance of C(X, y)
to some `-source is at most ε.
Definition 2.11. A function C : {0, 1}n × {0, 1}d → {0, 1}m is a (k → `, ε)-somewhere-condenser if for
every k-source X, the vector hC(X, y)iy∈{0,1}d is ε-close to a somewhere `-source. When convenient, we
call C a rate-(k/n → `/m, ε)-somewhere-condenser.
Note that a (k → `, ε)-strong-condenser is a (k → `, ε)-somewhere-condenser. We will also need the
following.
Lemma 2.12. If C : {0, 1}n × {0, 1}d → {0, 1}m is a (k → `, ε)-somewhere-condenser, then it is a
(2k , (1 − ε)2`−m )-disperser.
Proof. This follows because a distribution which is ε-close to an `-source must have a support of size at
least (1 − ε)2` .
When composing condensers, we will need the following type of lemma.
Lemma 2.13. Suppose Z1 is ε1 -close to an `1 -source, and for all z1 ∈ supp(Z1 ), the distribution (Z2 |
Z1 = z1 ) is ε2 -close to an `2 -source. Then Z1 ◦ Z2 is ε1 + ε2 -close to an `1 + `2 -source.
Proof. Let W1 be an arbitrary `1 -source which is ε1 -close to Z1 . For w1 ∈ supp(Z1 ) ∩ supp(W1 ), define
the distribution of (W2 | W1 = w1 ) to be an arbitrary `2 -source which is ε2 -close to (Z2 | Z1 = w1 ).
For w1 ∈ supp(W1 ) \ supp(Z1 ), define the distribution of (W2 | W1 = w1 ) to be the uniform distribution.
Then W1 ◦W2 is an `1 + `2 -source, which is ε1 + ε2 -close to Z1 ◦ Z2 ,
We build extractors by first condensing and then applying a weaker extractor. The idea of condensing
before extracting was used in [44, 47], and a simple lemma from [47] shows that this works.
0
Lemma 2.14 ([47]). Suppose that C : {0, 1}n × {0, 1}d1 → {0, 1}n is an efficient (strong) (k → `, ε1 )-
0
condenser, and Ext : {0, 1}n × {0, 1}d2 → {0, 1}m is an efficient (strong) (`, ε2 )-extractor. Then
Ext0 (x, y1 ◦ y2 ) = Ext(C(x, y1 ), y2 )
is an efficient (strong) (k, ε1 + ε2 )-extractor.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 110
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
2.8 Sum-product theorem
The following sum-product theorem underlies our condensers.
Theorem 2.15 ([11, 10]). There is a constant α > 0 such that for any field F = Fq where q is either
prime or 2 p for p prime, the following holds. For any non-empty A ⊂ F, |A| < q.9 ,
max(|A + A|, |A · A|) = Ω(|A|1+α ) .
Here the .9 can be increased to any constant less than 1, but the constant α will likely decrease.
Note that for q = 2 p , when A = {0, 1} then A + A = A · A = A; however, the Ω handles this problematic
case. We use results based on earlier versions of this theorem, when the full bounds were not known to
hold for fields of size 2 p . Although the result quoted above isn’t apparent for such fields in the credited
papers, it follows from Corollary 2.56 of [50], which credits those papers. For the best constant α as of
this writing see [33]. For a self-contained exposition of the prime case, see [23].
3 Disperser construction
We first use random walks on expanders to construct low-degree dispersers for high min-entropy. This
construction could work for any min-entropy rate bigger than 1/2, but to output almost all the random-
ness we need rate close to 1.
Proposition 3.1. For any α > 0, there is a β , c0 > 0 such that for any c = c(n) ≥ c0 , there is an efficient
family of strong (K = N 1−β , 2−c )-dispersers DIS : [N = 2n ] × [D] → [M = 2m ] such that D ≤ αn/c and
m ≥ (1 − α)n. (Let γ > 0 be the constant from Section 2.5. We can take c0 = 2/γ and β = αγ/5.)
Proof. We use the disperser of [1]. Set s = 2−c , and m = (1 − α)n. Let G be a 2c -regular 2−γc -expander
on [2m ] (see Section 2.5). To find the neighbors of a vertex u ∈ [2n ], use the n bits defining u to choose
a random vertex v0 ∈ [2m ] and then take a random walk v1 , . . . , vD on G. Connect u to v1 , . . . , vD . We
ignore v0 so that we cleanly get n = m + Dc, and D = (n − m)/c = αn/c.
First consider when the bits describing the random walk are uniformly random. In this case we can
use the tight analysis given by Kahale [30]. For S ⊆ [2m ] and s = |S|/2m , Kahale showed that
Pr[(∀i)vi ∈ S] ≤ s(s + (1 − s)λ )D−1 < (s + λ )D .
Since s = 2−c < 2−γc , this probability is less than 2(1−γc)D ≤ 2−(γ/2)cD ≤ 2−(γ/2)αn .
When the bits describing the random walk are chosen from a source with min-entropy (1 − β )n,
each string which before had probability 2−n now has probability at most 2β n · 2−n . Therefore, the error
probability grows by at most 2β n , and hence is at most 2(β −γα/2)n . Therefore, this is a (K = N 1−β , s)-
disperser for any β < γα/2.
We still need to show that this disperser is strong. To do this, we must consider the situation where
instead of one S we now have D such Si , |Si | = si 2m , where the average of the si is at most s. By the
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 111
D. Z UCKERMAN
result of Kahale given as Theorem A.5 in [22], for a uniformly random walk
s
√ D q D
Pr[(∀i)vi ∈ Si ] ≤ s1 sD ∏ si + (1 − si )λ 2 ≤ ∏(λ 2 + (1 − λ 2 )si )
i=2 i=1
!D/2
1 D 2
≤ ∑ (λ + (1 − λ 2 )si )
D i=1
≤ (λ 2 + s)D/2 .
The third inequality follows from the arithmetic-geometric mean. This bound (s + λ 2 )D/2 is at most the
square root of Kahale’s earlier bound, so it’s at most 2−(γα/4)n . By choosing β < γα/4 the proposition
follows.
To give a construction for all positive entropy rates, we use the following theorem, which follows
from the condenser in [5] or [43]. While [5] only gives an ordinary disperser, by Lemma 2.6 it is also a
strong disperser for essentially the same parameters, since D is constant.
Theorem 3.2 ([5, 43]). For any β , δ > 0, there is an efficient family of rate-(δ → 1 − β , ε = 2−Ω(n) )-
somewhere-condensers C : [N = 2n ] × [D] → [M = 2m ] where D = O(1) and m = Ω(n). For subconstant
δ = δ (n) the dependence is D = (1/δ )O(1) and m = δ O(1) n.
Remark 3.3. In the original paper, the construction for subconstant δ required a large prime. How-
ever, there is no longer a need for this, given the new sum-product theorem for fields of size 2 p (see
Subsection 2.8).
Applying Lemmas 2.12 and 2.6, we deduce
Corollary 3.4. For any β , δ > 0, there is an efficient family of strong (K = N δ , M −β )-dispersers DIS :
[N = 2n ] × [D] → [M = 2m ] where D = O(1) and m = Ω(n).
We can now give our disperser construction, although for now we obtain output length a small
constant fraction of δ n, rather than almost all of it.
Theorem 3.5. For any δ > 0 and s = s(n) > 0, there is an efficient family of strong (K = N δ , s)-
dispersers DIS : [N = 2n ] × [D] → [M = 2m ] such that D = O(n/ log s−1 ) and m = Ω(n). For subconstant
δ = δ (n) the dependence is D = (1/δ )O(1) n/ log s−1 and m = δ O(1) n.
0
Proof. Let DIS1 : [N = 2n ] × [D1 = O(1)] → [N 0 = 2n ] be an efficient strong (K = N δ , (N 0 )−.1 )-disperser
from Corollary 3.4, with n0 = Ω(n). Let DIS2 : [N 0 ] × [D2 ≤ n0 / lg s−1 ] → [M = 2m ], be an efficient
strong (K 0 = (N 0 ).9 , s)-disperser given by Proposition 3.1, with m = n0 /2. Applying Lemma 2.7 yields
the desired disperser.
To improve the output length to (1 − α)δ n, we need to use better condensers, and we defer the proof
to the next section.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 112
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
4 Extractor construction
Readers interested solely in the inapproximability results can skip directly to Section 6, as the current
dispersers suffice to prove those results.
Our extractor construction is essentially the same as our disperser construction. We first show how
to extract when the entropy rate is close to 1, by using random walks on expanders. Then we use Raz’s
recent condenser [43] to reduce to the high-entropy case.
Proposition 4.1. For all α, ε > 0, there exists β > 0 such that there is an efficient family of (k =
(1 − β )n, ε)-extractors Ext : {0, 1}n × {0, 1}d → {0, 1}m with m ≥ (1 − α)n and D = 2d ≤ αn.
Proof. Set m = (1 − α)n and c = 3 (say). Let G be a 2c -regular λ -expander on [2m ] with λ bounded
away from 1 (see Section 2.5). To find the neighbors of a vertex u ∈ [2n ], use the n bits defining u to
choose a random vertex v0 ∈ [2m ] and then take a random walk v1 , . . . , vD on G. Connect u to v1 , . . . , vD .
As before, n = m + Dc, and D = (n − m)/c = αn/c.
Let S ⊆ [2m ] have density µ = |S|/2m . First consider when the bits describing the random walk are
chosen uniformly, and let the random variable µ̂ denote the fraction of vi which are in S. Gillman [21]
(see also Kahale [31]) proved a Chernoff bound for random walks on expanders. We use the improved
constants obtained by Healy [27]:
Pr[|µ̂ − µ| ≥ ε] ≤ 2 exp(−(1 − λ )ε 2 D/4) .
(Dinwoodie [14] essentially improved the constant 4 above to 2, but only states it from a worst-case
vertex so there is another term.)
For large enough n (to get rid of the multiplicative 2), this error is at most 2−an for a = (1 −
λ )ε 2 α/(4c). When the bits describing the random walk are chosen from a source with min-entropy
(1 − β )n, the error probability grows by at most 2β n . Thus this is a (k = (1 − β )n, ε)-extractor for
β < a.
We can make these extractors strong by using a better Chernoff bound.
Proposition 4.2. For all α, ε > 0, there exists β > 0 such that there is an efficient family of strong-
(k = (1 − β )n, ε)-extractors Ext : {0, 1}n × {0, 1}d → {0, 1}m with m ≥ (1 − α)n and D = 2d ≤ αn.
Proof. We use the same construction. For the proof, we must now show near uniformity over [D] × [2m ].
We therefore consider S ⊆ [D] × [2m ], so S = ∪i {i} × Si . Again consider when the bits describing the
random walk are chosen uniformly, and now let the random variable µ̂ denote the fraction of vi which
are in Si . Wigderson and Xiao [52] improved Gillman’s theorem above for this case. We again use
Healy’s improved constants [27]):
Pr[|µ̂ − µ| ≥ ε] ≤ 2 exp(−(1 − λ )ε 2 D/4) .
We can then conclude with the same argument as above.
For dispersers, we combined the high-entropy construction with somewhere-condensers from The-
orem 3.2. For extractors, we need to use the improved strong condenser due to Raz [43].
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 113
D. Z UCKERMAN
Theorem 4.3 ([43]). For any constants β , δ , ε > 0, there is a constant d such that there is an efficient
rate-(δ → (1 − β ), ε)-strong condenser C : {0, 1}n × {0, 1}d → {0, 1}m such that m = Ω(n).
Applying Lemma 2.14 to Raz’s condenser and the extractor above, we obtain the desired theorem,
except that the output length is linear instead of the (1 − α)-fraction we claimed.
Theorem 4.4. For all δ , ε > 0 there is an efficient family of strong-(k = δ n, ε)-extractors Ext : {0, 1}n ×
{0, 1}d → {0, 1}m with m = Ω(n) and D = 2d = O(n).
5 Improving the output length
The results in this section were obtained jointly with Avi Wigderson.
We now would like to obtain output length (1 − α)k, for an arbitrary α > 0, while maintaining the
linear degree. The initial idea is to do a construction similar to that by Wigderson and the author [53]: if
the output length is significantly less than k, use an independent seed to extract more bits from the same
input. We can’t do this directly, because even two runs of the extractor gives degree Θ(n2 ), which is too
expensive. Yet we can achieve this with the condenser, which uses only a constant number of random
bits. Thus, our intermediate goal, which is interesting in its own right, is:
Theorem 5.1. For any constants α, β , δ , ε > 0, there is a constant d such that there is an efficient
rate-(δ → (1 − β ), ε)-strong condenser C : {0, 1}n × {0, 1}d → {0, 1}m such that m ≥ (1 − α)δ n.
Yet this theorem cannot be achieved by applying the above idea to Theorem 4.3. The reason is that
the error cannot be controlled. If the output length is γn, we would like to iterate about 1/γ times, but
we cannot do this if the initial error is bigger than γ. In Theorem 4.3, as well as Theorem 3.2, the output
length may depend on the error. Hence we construct an improved condenser, which follows from the
improved merger of Dvir and Raz [15]. In this merger, the output length doesn’t depend on the error.
Lemma 5.2. For any δ > 0, there exists γ > 0, such that for any ε > 0, there is a constant d such that
there is an efficient rate-(δ → (1 − δ ), ε)-strong condenser C : {0, 1}n × {0, 1}d → {0, 1}m such that
m ≥ γn.
Proof. Fix δ > 0. By Theorem 3.2, there is an efficient rate-(δ → 1 − δ /2, ε1 = 2−Ω(n) ) somewhere-
condenser C1 : {0, 1}n × {0, 1}d1 → {0, 1}m1 , where d1 = O(1) and m1 = Ω(n). By the main theorem
d
of [15], there is a “strong merger” M : ({0, 1}m1 )2 1 × {0, 1}d → {0, 1}m with d = f (d1 ) = O(1) and
m = Ω(m1 ) such that whenever the input X1 on ({0, 1}m1 )2 1 is a somewhere rate (1 − δ /2)-source, then
d
the average over y ∈ {0, 1}d of the distance of M(X1 , y) to the closest rate (1 − δ )-source is at most ε/2.
The length m may be chosen independently of ε, although d depends on ε. Hence the required strong
condenser is C(x, y) = M(hC1 (x, y1 iy1 ∈{0,1}d1 , y).
The following lemma is the condenser analogue to the corresponding extractor lemma in [53].
Lemma 5.3. Suppose that C1 : {0, 1}n × {0, 1}d1 → {0, 1}m1 is a strong (k → `1 , ε1 )-condenser and
C2 : {0, 1}n × {0, 1}d2 → {0, 1}m2 is a strong (k − m1 − s → `2 , ε2 )-condenser. Then C : {0, 1}n ×
{0, 1}d1 +d2 → {0, 1}m1 +m2 , given by
C(x, y1 ◦ y2 ) = C1 (x, y1 ) ◦C2 (x, y2 ) ,
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 114
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
is a strong (k → `1 + `2 , ε1 + ε2 + 2−s )-condenser.
Proof. Let X be a k-source. For y ∈ {0, 1}di , let εiy denote the minimum distance of Ci (X, y) to some
`i -source. Fix y1 ∈ {0, 1}d1 . Let S denote the set of low-probability elements in the output:
S = {z | Pr[C1 (X, y1 ) = z] ≤ 2−(m1 +s) } .
X
Then Pr[C1 (X, y1 ) ∈ S] ≤ |S|2−(m1 +s) ≤ 2−s . For z 6∈ S, X conditioned on C1 (X, y1 ) = z is a (k − m1 − s)-
source. Hence, under such conditioning, for each y2 ∈ {0, 1}d2 , C2 (X, y2 ) is within ε2y2 of some `2 -source.
Putting this together as in Lemma 2.13, C(X, y1 ◦ y2 ) is within ε1y1 + 2−s + ε2y2 of some `1 + `2 -source.
Since the average of εiyi is at most εi , this completes the proof of the lemma.
Applying this lemma inductively, we can show:
Lemma 5.4. Suppose C : {0, 1}n × {0, 1}d → {0, 1}m is an efficient strong (k → `, ε)-condenser. Then
for any positive integers s,t, we can construct C0 : {0, 1}n × {0, 1}td → {0, 1}tm , an efficient strong
(k + (t − 1)m + s → t`,tε + (t − 1)2−s )-condenser.
Proof. We prove this by induction on t. For the base case t = 1 we can take C0 = C. Now assume the
lemma for a given t. Set C1 to be the condenser given by the lemma for t, and set C2 = C. Applying
Lemma 5.3 gives the condenser for t + 1.
We can now prove Theorem 5.1. We would like to condense additional entropy, as long as there
is αδ n entropy left in the source. We also want the output entropy rate to be 1 − β , and if in each
iteration we have this entropy rate, then overall we do as well. These two goals mean we should use a
condenser converting rate αδ to rate 1 − β . This condenser has some output length γn, so we need to
iterate 1/γ times. This determines the error we need, which is why it is crucial we can pick the error
after knowing γ.
Proof of Theorem 5.1. Let α, β , δ , ε > 0 be given. By Lemma 5.2, for some γ > 0 there is an efficient
strong rate-(αδ → (1 − β ), ε 0 )-condenser C : {0, 1}n × {0, 1}d → {0, 1}m , where ε 0 will be chosen later
and m ≥ γn. Set t = (1−α)δ /γ and apply Lemma 5.4 with an s to be chosen later. This gives an efficient
strong (δ n − γn + s → (1 − β )(tm), iε 0 + 2−s )-condenser C0 : {0, 1}n × {0, 1}id → {0, 1}tm . Choosing
s = γn and ε 0 small enough so tε 0 + 2−s ≤ ε gives the theorem.
Combining our condenser from Theorem 5.1 with our extractor from Proposition 4.1 via
Lemma 2.14, we obtain our main extractor construction:
Theorem 1.7. For all constant α, δ , ε > 0 there is an efficient family of strong (k = δ n, ε)-extractors
Ext : {0, 1}n × {0, 1}d → {0, 1}m with m ≥ (1 − α)δ n and D = 2d = O(n).
By combining the same condenser with the earlier disperser of Proposition 3.1, we obtain our main
disperser construction:
Theorem 1.9. For all constant α, δ > 0 and s = s(n) > 0, there is an efficient family of strong (K =
N δ , s)-dispersers DIS : [N = 2n ] × [D] → [M = 2m ] such that D = O(n/ log s−1 ) and m ≥ (1 − α)δ n. For
subconstant δ = δ (n), the dependence is D = (1/δ )O(1) n/ log s−1 and m = δ O(1) n.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 115
D. Z UCKERMAN
6 Max Clique
In this section, we show how our dispersers yield inapproximability results for M AX C LIQUE. We
assume some familiarity with PCPs. Since the inapproximability of M AX C LIQUE follows from the
proof of the inapproximability of C HROMATIC N UMBER, readers not familiar with PCPs may prefer to
read the next section, which doesn’t use them.
Historically, Feige et al. [18] were the first to show how to obtain inapproximability results for M AX
C LIQUE using PCPs. Bellare, Goldreich, and Sudan [6] showed that free bit complexity is the parameter
of a PCP which gives the best inapproximability results.
Definition 6.1. FPCPs (r, f ) is the class of promise problems recognized by PCP verifiers using r random
bits and f free bits, achieving perfect completeness and soundness s.
Theorem 6.2 ([6, 18]). If NP ⊆ FPCPs (r, f ), then it is NP-hard to distinguish whether a graph on 2r+ f
vertices has clique number at least 2r or at most s2r .
Håstad [25] showed how to reduce the soundness by paying only a tiny amount in the free bit
complexity. Specifically, he showed:
Theorem 6.3 ([25]). For any f¯ > 0, there is an ` such that NP ⊆ FPCP2−` (O(log n), f¯`).
The quantity f¯ is called the amortized free bit complexity, and can be less than 1 (Håstad’s result
shows it can be any positive constant).
The following follows from Theorem 6.2 and the amplification of a PCP via a good disperser, as first
suggested in [54].
Lemma 6.4. Suppose NP ⊆ FPCPs (r, f ) and there is a polynomial-time constructible (K, s)-disperser
DIS : [2R ] × [D] → [2r ]. Then NP ⊆ FPCPK/2R (R, D f ), and hence it is NP-hard to distinguish whether a
graph on 2R+D f vertices has clique number at least 2R or clique number at most K.
This suffices to prove our theorem.
Theorem 1.1. It is NP-hard to approximate M AX C LIQUE to within n1−ε for any ε > 0.
Proof. Equivalently, we will show a factor of n1−2ε . Fix ε > 0. Theorem 1.9 says that for any s =
s(n) there is an efficient family of (K = N ε , s)-dispersers of degree D ≤ c(log N)/ log s−1 , for some
c = c(ε). Let f¯ ≤ ε/c, and apply Theorem 6.3 to get an ` and r = r(n) = O(log n) such that NP ⊆
FPCP2−` (r, f¯`). Now let s = 2−` , so there is an efficient (K = (2R )ε , 2−` )-disperser DIS : [2R ] × [D] →
[2r ]. Apply Lemma 6.4 with this disperser, and note that D f ≤ (cR/`) · (` f¯) = f¯ · cR ≤ εR. Hence it is
NP-hard to distinguish clique number at least 2R from clique number at most 2εR in graphs on 2(1+ε)R
vertices. Moreover, since the output length is linear in the input length, R = O(log n), so the reduction
is polynomial time.
To obtain inapproximability up to an n1−o(1) factor, we can use the following theorem by Håstad and
Khot [26], which is basically the same as that obtained by Samorodnitsky and Trevisan [45] but gives
perfect completeness.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 116
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
Theorem 6.5 ([26]). For any ` = `(n) which is one less than a perfect square,
√
NP ⊆ FPCP2−` (O(` log n), 2 ` + 1) .
We can now prove:
1−γ
Theorem 1.3. For some γ > 0, it is NP̃-hard to approximate M AX C LIQUE to within n/2(log n) .
Proof. Set ε = ε(n) = 1/ log n. By Theorem 3.5 (or the stronger Theorem 1.9), there is a c such
that for any s = s(n) there is a polynomial-time constructible family of (K = N ε , s)-dispersers of de-
gree D ≤ (log n)c (log N)/ log s−1 . Let ` = 9(log n) √
2(c+1) and s = 2−` . Apply Theorem 6.5 to get
r = r(n) = polylog(n) such that NP ⊆ FPCPs (r, 3 `). We’ll use the polynomial-time constructible
(K = (2R )ε , 2−` )-disperser
√ DIS : [2R ] × [D] → [2r ]. Apply Lemma 6.4 with disperser DIS, and note that
D f ≤ (R(log n)c /`) · (3 `) = R/ log n = εR. Hence it is NP-hard to distinguishing clique number at
least 2R from clique number at most 2R/ log n in graphs on 2(1+1/ log n)R vertices. Since R = polylog(n),
the theorem follows.
7 Chromatic Number
Now we show how our dispersers imply the NP-hardness of approximating C HROMATIC N UMBER to
within n1−ε for any ε > 0. We derandomize Feige’s and Kilian’s proof [19] of the same inapproxima-
bility ratio but under the stronger assumption that NP is not in ZPP. As in their proof, we work with
the fractional chromatic number χ f , which up to logarithmic factors is the same as the chromatic num-
ber χ [35]. They also make use of the independence number α. Just as α(G)χ(G) ≥ |V (G)|, so too is
α(G)χ f (G) ≥ |V (G)| (here V (G) denotes the vertices of G).
Feige and Kilian start with a graph G (from a family of graphs) which has a constant hardness ratio:
either G has chromatic number at least c or at most c0 < c. They actually need c0 = cγ , where γ > 0 is
arbitrary, as well as a corresponding bound on the independence number α.
Theorem 7.1 ([19]). For all γ > 0, there is an s > 0, such that there is a polynomial-time reduction
from an NP-complete language L to chromatic number with the following properties. On input x, the
algorithm outputs a graph G = (V, E) such that
1. If x ∈ L then χ f (G) ≤ s−γ ;
2. If x 6∈ L then α(G) < s|V |, and hence χ f (G) > 1/s.
(The parameter s is not exactly the soundness of the PCP; rather, it is the soundness times 2− f , where
f is the free bit complexity. Also, Feige and Kilian don’t state this as a theorem, but it can be deduced
from their Lemma 2 and the parameters achieved in their Section 5.6. They state their parameters as:
for any γ, ` > 0, they can set s = O(2−` ) and if x ∈ L then χ f (G) ≤ 23γ`+1 . This is equivalent to our
statement above, for a slightly different choice of γ.)
Feige and Kilian next amplify the hardness ratio using randomized graph products. That is, they
take a suitably-sized random subgraph G0 of the product graph GD which has hardness ratio |V (G0 )|1−ε .
GD is defined with respect to the following “OR” graph product.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 117
D. Z UCKERMAN
Definition 7.2. For graphs G = (V, E) and H = (W, F), define the graph G × H as having vertex set
V ×W , and edges {(v, w), (v0 , w0 )} where {v, v0 } ∈ E or {w, w0 } ∈ F.
Note that (v1 , . . . , vD ) is adjacent to (w1 , . . . , wD ) in GD if any (vi , wi ) is an edge in G. It is straight-
forward to show that α(G × H) = α(G) · α(H). Using the definition of χ f as a linear program and linear
programming duality, Feige showed that χ f (G × H) = χ f (G) · χ f (H) [17].
We derandomize the randomized graph powering. This was done earlier in the clique setting [2], but
the results there are not tight enough. On the other hand, for cliques, two types of bounds are needed
– one if the clique number is large, and one if it’s small. For chromatic number, one of the two cases
becomes easy. If χ f (G) is small, it will suffice to use the trivial bound χ f (G0 ) ≤ χ f (GD ) = χ f (G)D .
We can define a derandomized graph powering of G = (V, E) with respect to any disperser DIS :
X × [D] → V as follows. Define DIS(x) = (DIS(x, 1), DIS(x, 2), . . . , DIS(x, D)) and DIS(X) = {DIS(x) |
x ∈ X}. Now define the graph DIS(GD ) to be the induced subgraph of GD on vertex set DIS(X).
Lemma 7.3. Given a graph G = (V, E) and a disperser DIS with degree D, let G0 = (V 0 , E 0 ) = DIS(GD ).
Then
1. χ f (G0 ) ≤ (χ f (G))D .
2. If α(G) < s|V | and DIS is a strong (K, s)-disperser, then α(G0 ) < K, and hence χ f (G0 ) > |V 0 |/K.
Proof. The first part follows because χ f (G0 ) ≤ χ f (GD ) = (χ f (G))D . For the second part, suppose
α(G0 ) ≥ K, and let X be an independent set in G0 of size K. Note that Γi (X), as defined in Lemma 2.8,
corresponds to the set of ith coordinates of X. By the strong disperser property, for some i ∈ [D],
|Γi (X)| ≥ s|V | > α(G). Hence Γi (X) is not an independent set in G, so it contains an edge, say {vi , wi }.
If vi is the ith coordinate of v, and wi is the ith coordinate of w, then because we are using the OR
graph product, {v, w} is an edge in G0 . Since v, w ∈ X, this contradicts our assumption that X was an
independent set.
We are now ready to prove our theorem.
Theorem 1.2. It is NP-hard to approximate C HROMATIC N UMBER to within n1−ε for any ε > 0.
Proof. Fix ε > 0. Theorem 1.9 says that for any s = s(n) there is an efficient family of strong (K = N ε , s)-
dispersers of degree D ≤ cn/ log s−1 , for some c = c(ε). Set γ = ε/c, and use the Feige-Kilian reduction,
which comes with an s = s(γ). Using this s, apply Lemma 7.3 using an efficient strong (K = N ε , s)-
disperser. In polynomial time we construct a graph G0 on N vertices such that if x ∈ L,
χ f (G0 ) ≤ s−γD ≤ 2γcn = N ε .
If x 6∈ L, then α(G0 ) ≤ N ε , so χ f (G0 ) ≥ N 1−ε . Thus it is NP-hard to distinguish graphs with fractional
chromatic number N ε from graphs with fractional chromatic number N 1−ε . Converting to chromatic
number loses only a logarithmic factor, so the theorem follows.
To derandomize Khot’s results, we use his reduction in place of Theorem 7.1:
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 118
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
Theorem 7.4 ([34]). For any β > 0, there is a quasi-polynomial-time reduction from an NP-complete
language L to C HROMATIC N UMBER with the following properties. On input x of size n, the algorithm
outputs a graph G = (V, E) such that
1+3β
1. |V | ≤ 2(log n) ;
β
2. If x ∈ L then χ f (G) ≤ 2(log n) ;
2β
3. If x 6∈ L then α(G) < 2−(log n) |V |.
We can now show:
Theorem 1.4. For some γ > 0, it is NP̃-hard to approximate C HROMATIC N UMBER to within
1−γ
n/2(log n) .
Proof. We use the polynomial-time constructible (N δ , s)-strong disperser from Theorem 1.9, with s =
2β
2−(log n) and δ to be chosen shortly. This has degree D ≤ (log N)/(δ c (log n)2β ). Set δ = (log n)−β /2c .
Applying Lemma 7.3, it is NP̃-hard to distinguish between graphs on N vertices with chromatic number
β −β /2
N δ from those with chromatic number 2(log n) D ≤ N (log n) .
8 Simplifying and strengthening additive number theory applications
We now give our simple one-bit condenser and improve other lemmas from [4, 5, 9]. We first define
incidences of lines and points.
Definition 8.1. For P a set of points and L a set of lines, I(P, L) denotes the number of incidences, i.e.,
the number of ordered pairs (p, `) where the point p lies on the line `.
We rely heavily on the following theorem on point-line incidences. Bourgain, Katz, and Tao [11]
showed how this theorem follows from the sum-product theorem (see Section 2.8). The constant 1.9
below can be increased to any constant less than 2, but the constant α will likely decrease.
Theorem 8.2 (Incidence Theorem [11, 10]). Let F = Fq , where q is either prime or 2 p for p prime. Let
P, L be sets of points and lines in F 2 of cardinality at most M ≤ p1.9 . Then there exists an α > 0 such
that the number of incidences
I(P, L) = O(M 3/2−α ) .
8.1 Condensing with one random bit
Barak et al. [5] consider a condenser which uses two extra bits of randomness; here we show that one
bit of randomness suffices. Of course, one bit is necessary, so this is optimal. Our proof is also simpler,
proceeding directly from the Incidence Theorem 8.2. There is nothing special about the constant .9
below; any constant less than 1 will do.
Our condenser is simple to describe. We work over a field F = Fq , where q = 2 p for p prime. Define
the point-line incidence graph as the bipartite graph G = (V,W, E) with vertices V = F 2 the set of points,
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 119
D. Z UCKERMAN
and W the set of lines over F, and (p, `) is an edge iff p and ` are incident. Our condenser is based on
the function h : E → V × W which maps an edge to its two endpoints. An equivalent view of h is the
map from F 3 to (F 2 )2 which maps (a, b, c) to ((b, ab + c), (a, c)). This is because the point (b, ab + c)
lies on the line y = ax + c.
Our condenser C : F 3 × {0, 1} → F 2 is simply C(e, i) = h(e)i . The two-bit condenser of Barak, et al.
is very similar: their corresponding h maps (a, b, c) to the length 4 vector (a, b, c, ab + c).
Theorem 8.3. Suppose δ ≤ .9 and qδ = ω(1). The function C above is a rate-(δ → (1 + α/2)δ , ε)-
somewhere-condenser, where ε = q−αδ /20 . Here α is the constant from the Incidence Theorem 8.2.
Before we proceed, it is convenient to introduce a modified notion of somewhere-random source,
which we call somewhere light.
Definition 8.4. A vector of sources X = (X1 , . . . , X` ) is ε-close to somewhere-k-light if the probability,
when (x1 , . . . , x` ) is output according to X, that no xi are light is at most ε. We say xi is light if Pr[Xi =
xi ] ≤ 2−k .
The following lemma describes the relationship between this notion and that of somewhere-random.
Lemma 8.5. Assume `2−t < 1 − ε. If X = (X1 , . . . , X` ) is ε-close to somewhere-k-light, then X is ((` −
1)2−t + ε)-close to a somewhere-(k − t)-source.
Proof. Partition the support of X into ` + 1 bins so that bin i contains vectors (x1 , . . . , x` ) where xi is light
(break ties arbitrarily), and bin 0 contains vectors with no light coordinates. The probability of a bin is
the sum of the probabilities of vectors in the bin. By assumption, bin 0 has probability at most ε. Let
bin(x) denote the bin of x. Consider any bin i 6= 0 with probability at least 2−t (since `2−t < 1 − ε there
is at least one such bin). For any (x1 , . . . , x` ) in bin i,
Pr[Xi = xi | bin(X) = i] ≤ Pr[Xi = xi ]/ Pr[bin(X) = i] ≤ 2t · 2−k .
Hence, if we let Y i denote the distribution of X conditional on bin(X) = i, we get that Yii has min-entropy
at least k − t, and hence Y i is a somewhere (k − t)-source. For any bin i with probability less than 2−t ,
and for i = 0, let Y i be the uniform distribution. Define the distribution Y = ∑i Pr[bin(X) = i]Y i . Then
Y is a somewhere (k − t)-source and the distance of X to Y comes only from bin 0 and bins with low
probability, and is at most ε + (` − 1)2−t .
We now work with the modified notion. The main idea is to convert the statistical problem to a
counting problem, which we do via the following lemma.
Lemma 8.6. If (X,Y ) is not ε-close to a somewhere-k-source, then there exists sets S ⊆ supp(X),T ⊆
supp(Y ), |S|, |T | < 2k+1 /ε, such that
Pr[X ∈ S ∧Y ∈ T ] > ε/2 .
Proof. Let r = k + lg(2/ε). By Lemma 8.5, (X,Y ) is not ε/2-close to somewhere-r-light. Setting
S = {s | X(s) > 2−r } and T = {t | Y (t) > 2−r } yields the lemma.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 120
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
We can now prove the theorem.
Proof of Theorem 8.3. Instead of C, we analyze the equivalent function h. We may assume that the
input to h is uniform on a set of edges of size K = 2k = q3δ , and set k0 = (1 + α/2)(2k/3). Suppose
the output (X,Y ) of h is not ε-close to a somewhere-k0 -source. Let P = S and L = T be the sets of size
0
less than K0 = 2k +1 /ε given by Lemma 8.6. Assuming without loss of generality that α ≤ .1, note that
K0 ≤ q2δ 1 + α/2 ≤ q1.8·1.05 < q1.9 .
We calculate the number of incidences I(P, L) in two ways. On the one hand, since each edge is an
incident point-line pair, and at least ε/2 fraction of these pairs lie in P × L, the number of incidences
I(P, L) ≥ εK/2. On the other hand, by the Incidence Theorem 8.2,
3/2−α
I(P, L) = O(K0 ) = O(K (1+α/2)(3/2−α)2/3 /ε 2 ) = O(K 1−α/6 /ε 2 ) .
Combining these, we get a contradiction for ε = K −α/20 , and the theorem is proved.
8.2 AB+C theorem from two sources
In this section and the next, we consider a scenario where we have several independent weak sources,
but no truly random seed. The sum-product theorem implies that if A, B, and C are sets of the same
size K, then the set AB +C is noticably bigger than K. Barak et al. [4] showed the significantly stronger
statistical statement: if A, B, and C are independent distributions with min-entropy k each, then the
entropy rate of AB +C is noticably larger than k.
Here we show how to improve the entropy rate with just two sources, by allowing A and C to be
correlated. Our proof is also simpler than that in [4]. Again, there is nothing special about the constant
.9 below; any constant less than 1 will do.
Theorem 8.7. Suppose δ ≤ .9 and qδ = ω(1). If (A,C) and B are output from independent rate-
δ -sources, where A, B,C are elements of a field F = Fq , where q is prime or 2 p where p is prime.
Then AB + C is q−αδ /2 -close to a rate-(1 + α)δ -source, where α is the constant from the Incidence
Theorem 8.2.
We prove this using the Incidence Theorem 8.2. The relevance of lines comes in viewing (a, c) as the
line y = ax + c. In order to get a suitable set of points, we use the following simple lemma. This lemma
is key in deducing a statistical theorem, which is about distributions, from the Incidence Theorem 8.2,
which just bounds set sizes.
Lemma 8.8. Suppose X is ε-far from a k-source. Then ∃S ⊆ supp(X), |S| < 2k , such that Pr[X ∈ S] ≥ ε.
Proof. Take S = {s | X(s) > 2−k }, so |S| < 2k . Lemma 2.2 implies that the distance of X to the closest
k-source is ∑s∈S (X(s) − 2−k ) ≤ Pr[X ∈ S].
We can now prove the theorem by taking the set of points to be B × S.
Proof of Theorem 8.7. Let (A,C) be output from a flat 2k-source, and B from an independent flat k-
source. Suppose AB + C is ε-far from a k0 source, where k0 = (1 + α)k. Let S be the set of size less
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 121
D. Z UCKERMAN
0
than K 0 = 2k given by Lemma 8.8. Define the set of lines L to be the support of (A,C), where (a, c) is
associated with the line ax + c. Let P be the set of points supp(B) × S.
We calculate the number of incidences in two different ways. On the one hand, note that when the
line (a, c) applied to b lands in S, it corresponds to an incidence. Since Pr[AB + C ∈ S] ≥ ε, and since
the distributions are flat,
I(P, L) ≥ ε|L| · | supp(B)| = εK 3 ,
where K = 2k ≤ |F|.9 . On the other hand, since |L| = K 2 ≤ |F|1.8 and |P| ≤ K · K 0 = K 2+α ≤ |F|1.9 , by
the Incidence Theorem 8.2
I(P, L) = O(K (2+α)(3/2−α) ) = o(K 3−α/2 ) .
Hence we may take ε = K −α/2 and the theorem follows.
8.3 Rate-improving function for two equal-length sources
Note that the previous theorem improves the rate from two independent sources, where one has twice
the length of the other. In this subsection, we do this from two sources of equal length, by giving
a statistical version of a theorem by Bourgain. Bourgain [9] showed that for a prime q, the function
g : Fq × Fq → Fq given by g(x, y) = x(x + y) has the following “expanding” property. For |A| ≥ |B| ≥ qδ ,
δ < 1, g(A, B) ≥ qδ +β for some β = β (δ ) > 0.1 With the new sum-product theorem holding also
for q = 2 p , p prime, Bourgain’s theorem will also hold in this case.
We show the statistical analogue of this theorem. Equivalently, our theorem says that the AB + C
theorem holds when C = A2 , and furthermore the entropy rate is measured with respect to the length of
A, rather than (A,C).
Theorem 8.9. Suppose δ ≤ .9 and qδ = ω(1). If X,Y are output from independent rate-δ -sources on
F = Fq , then g(X,Y ) is q−αδ /4 -close to a rate-(1 + α/2)δ -source. Here α is the constant from the
Incidence Theorem 8.2.
Proof. We follow Bourgain’s proof, but some care is required to make it statistical. Let X and Y be
independent random variables uniformly distributed over sets A and B of size qδ . Assume without loss
of generality that they don’t contain 0. Suppose g(X,Y ) is not ε-close to a δ + β -source, where we will
choose β and ε later. Let
S = {z ∈ F | Pr[g(X,Y ) = z] > q−(δ +β ) } ,
i. e., S is the set of size less than qδ +β guaranteed by Lemma 8.8, such that Pr[g(X,Y ) ∈ S] ≥ ε.
The difficulty in proving the theorem is that directly, this probability being at least ε does not give
many lines (in y), so we cannot apply the Incidence Theorem 8.2. We follow Bourgain and find many
more lines by exploiting the linearity in y.
To this end, we begin with a collision probability lower bound. Let
T = {y | Pr[g(X, y) ∈ S] ≥ ε/2} .
1 Bourgain’s proof also uses the Incidence Theorem 8.2, but it was done independently of our use of the Incidence Theo-
rem 8.2 in Subsections 8.1 and 8.2.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 122
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
Then |T | ≥ ε2 |B| ≥ ε2 qδ . Fix y0 ∈ T . Let Z be distributed as X, but independent of X and Y . Then
ε
Pr [g(X,Y ) = g(Z, y0 )] > Pr[g(Z, y0 ) ∈ S]q−(δ +β ) ≥ q−(δ +β ) .
X,Y,Z Z 2
Let X1 also be distributed as X, but independent of all previously defined random variables. We now
show that a function in both X, X1 , and Y , which is linear in Y , still has significant probability of being
in S. This will give us many more lines.
X1 X1
Pr [X(X +
X,X1 ,Z,Y Z
(X1 +Y ) − Z) ∈ S] ≥ ∑ Pr[X(X + y0 ) ∈ S] Pr[ Z (X1 +Y ) − Z = y0 ]
y0 ∈T
= ∑ Pr[X(X + y0 ) ∈ S] Pr[X1 (X1 +Y ) = Z(Z + y0 )]
y0 ∈T
ε ε ε3
> |T | · q−(δ +β ) > q−β .
2 2 8
Therefore, there is a fixed z such that
X1 ε3
Pr [X(X + (X1 +Y ) − z) ∈ S] > q−β . (8.1)
X,X1 ,Y z 8
This says there are many lines (linear in y) which, when applied to many values of y, land in S. This
will contradict the Incidence Theorem 8.2. In particular, let `x,x1 (y) denote the line
xx1 xx2
y + x2 + 1 − zx ,
z z
and let L denote the set of all such lines as x, x1 range over A.
Of course, |L| ≤ |A|2 = q2δ . We also show |L| ≥ q2δ /3 by observing that, for fixed z, w, there are at
most 3 nonzero solutions in x, x1 to
xx1
z =
z
xx2
w = x2 + 1 − zx .
z
We define the points P = B × S, so |P| < q2δ +β . By Equation (8.1) and the fact that the pairs (x, x1 )
ε 3 3δ −β
overcount lines by at most a factor of 3, the number of incidences is at least 24 q . By the Incidence
Theorem 8.2, the number of incidences is O(q(2δ +β )(3/2−α) ). Comparing these gives the theorem, with
β = αδ /2 and ε = q−αδ /4 .
Acknowledgements
I am grateful to Avi Wigderson for our joint work on Section 5, as well as for other useful discussions.
I also thank Ronen Shaltiel, Anup Rao, Mike Saks, Salil Vadhan, Madhu Sudan, and Jesse Kamp for
helpful discussions and comments. Finally, I thank the anonymous referees for careful readings and very
helpful comments.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 123
D. Z UCKERMAN
References
[1] * M. A JTAI , J. KOML ÓS , AND E. S ZEMER ÉDI: Deterministic simulation in LOGSPACE. In Proc.
19th STOC, pp. 132–140, 1987. [STOC:28395.28410]. 1.3, 3
[2] * N. A LON , U. F EIGE , A. W IGDERSON , AND D. Z UCKERMAN: Derandomized graph products.
Computational Complexity, 5:60–75, 1995. [Springer:r591795p150lj86q]. 7
[3] * S. A RORA , C. L UND , R. M OTWANI , M. S UDAN , AND M. S ZEGEDY: Proof verifica-
tion and the hardness of approximation problems. Journal of the ACM, 45:501–555, 1998.
[JACM:278298.278306]. 1.1
[4] * B. BARAK , R. I MPAGLIAZZO , AND A. W IGDERSON: Extracting randomness using few inde-
pendent sources. In Proc. 45th FOCS, pp. 384–393, 2004. [FOCS:10.1109/FOCS.2004.29]. 1.3,
8, 8.2
[5] * B. BARAK , G. K INDLER , R. S HALTIEL , B. S UDAKOV, AND A. W IGDERSON: Simulating
independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. In
Proc. 37th STOC, pp. 1–10, 2005. [STOC:1060590.1060592]. 1.3, 3, 3.2, 8, 8.1
[6] * M. B ELLARE , O. G OLDREICH , AND M. S UDAN: Free bits, PCPs, and nonapprox-
imability — towards tight results. SIAM Journal on Computing, 27(3):804–915, 1998.
[SICOMP:10.1137/S0097539796302531]. 1.1, 1.1, 6, 6.2
[7] * M. B ELLARE AND M. S UDAN: Improved non-approximability results. In Proc. 26th STOC, pp.
184–193, 1994. [STOC:195058.195129]. 1.1
[8] * R. B OPPANA AND M. H ALLDORSSON: Approximating maximum independent sets by exclud-
ing subgraphs. Bit, 32:180–196, 1992. 1.1
[9] * J. B OURGAIN: More on the sum-product phenomenon in prime fields and its applications. In-
ternational Journal of Number Theory, 1:1–32, 2005. [WorldSci:10.1142/S1793042105000108].
1.3, 8, 8.3
[10] * J. B OURGAIN , A. G LIBICHUK , AND S. KONYAGIN: Estimates for the number of sums and
products and for exponential sums in fields of prime order. Journal of the London Mathematical
Society, 73:380–398, 2006. [Cambridge:10.1112/S0024610706022721]. 1.3, 2.15, 8.2
[11] * J. B OURGAIN , N. K ATZ , AND T. TAO: A sum-product estimate in finite fields, and applications.
Geometric and Functional Analysis, 14:27–57, 2004. [Springer:s00039-004-0451-1]. 1.3, 2.15,
8, 8.2
[12] * B. C HOR AND O. G OLDREICH: Unbiased bits from sources of weak randomness and
probabilistic communication complexity. SIAM Journal on Computing, 17(2):230–261, 1988.
[SICOMP:10.1137/0217015]. 2.4
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 124
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
[13] * A. C OHEN AND A. W IGDERSON: Dispersers, deterministic amplification, and weak random
sources. In Proc.30th FOCS, pp. 14–19, 1989. 1.3
[14] * I.H. D INWOODIE: A probability inequality for the occupation measure of a reversible markov
chain. Annals of Applied Probability, 5:37–43, 1995. 4
[15] * Z. DVIR AND R. R AZ: Analyzing linear mergers. Technical Report TR05-025, Electronic
Colloquium on Computational Complexity, 2005. [ECCC:TR05-025]. 5, 5
[16] * L. E NGEBRETSEN AND J. H OLMERIN: Towards optimal lower bounds for clique and chro-
matic number. Theoretical Computer Science, 299:537–584, 2003. [TCS:10.1016/S0304-
3975(02)00535-2]. 1.1
[17] * U. F EIGE: Randomized graph products, chromatic numbers, and the Lovasz θ function. Combi-
natorica, 17:79–90, 1997. [Springer:x785787h43724566]. 7
[18] * U. F EIGE , S. G OLDWASSER , L. L OVASZ , S. S AFRA , AND M. S ZEGEDY: Interactive
proofs and the hardness of approximating cliques. Journal of the ACM, 43:268–292, 1996.
[JACM:226643.226652]. 1.1, 6, 6.2
[19] * U. F EIGE AND J. K ILIAN: Zero knowledge and the chromatic number. Journal of Computer
and System Sciences, 57:187–199, 1998. [JCSS:10.1006/jcss.1998.1587]. 1.1, 7, 7.1
[20] * O. G ABBER AND Z. G ALIL: Explicit construction of linear sized superconcentrators. Journal of
Computer and System Sciences, 22:407–420, 1981. [JCSS:10.1016/0022-0000(81)90040-4]. 2.5
[21] * D. G ILLMAN: A Chernoff bound for random walks on expander graphs. SIAM Journal on
Computing, 27:1203–1220, 1998. [SICOMP:10.1137/S0097539794268765]. 1.3, 4
[22] * O. G OLDREICH: A sample of samplers – a computational perspective on sampling (sur-
vey). Technical Report TR97-020, Electronic Colloquium on Computational Complexity, 1997.
[ECCC:TR97-020]. 3
[23] * B. G REEN: Sum-product estimates. Unpublished lecture notes. Available at author’s website,
2005. 2.8
[24] * M. H ALLDORSSON: A still better performance guarantee for approximate graph coloring. In-
formation Processing Letters, 45:19–23, 1993. [IPL:10.1016/0020-0190(93)90246-6]. 1.1
[25] * J. H ÅSTAD: Clique is hard to approximate within n1−ε . Acta Mathematica, 182:105–142, 1999.
[Springer:m68h3576646ll648]. 1.1, 6, 6.3
[26] * J. H ASTAD AND S. K HOT: Query efficient PCPs with perfect completeness. In Proc. 42nd
FOCS, pp. 610–619, 2001. [FOCS:10.1109/SFCS.2001.959937]. 6, 6.5
[27] * A. H EALY: Randomness-efficient sampling within NC1 . In Proc. 10th Intern. Workshop on
Randomization and Computation (RANDOM), pp. 398–409, 2006. [Springer:b773545612310728].
4, 4
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 125
D. Z UCKERMAN
[28] * S. H OORY, N. L INIAL , AND A. W IGDERSON: Expander graphs and their applications. Bulletin
of the American Mathematical Society, 43:439–561, 2006. 2.5
[29] * R. I MPAGLIAZZO AND D. Z UCKERMAN: How to recycle random bits. In Proc.30th FOCS, pp.
248–253, 1989. 1.3
[30] * N. K AHALE: Eigenvalues and expansion of regular graphs. Journal of the ACM, 42:1091–1106,
1995. [JACM:210118.210136]. 3
[31] * N. K AHALE: Large deviation bounds for Markov chains. Combinatorics, Probability, and Com-
puting, 6:465–474, 1997. [Cambridge:10.1017/S0963548397003209]. 1.3, 4
[32] * R. M. K ARP: Reducibility among combinatorial problems. In R. E. M ILLER AND J. W.
T HATCHER, editors, Complexity of Computer Computations, pp. 85–103. Plenum Press, New
York, 1972. 1.1
[33] * N. K ATZ AND C.-Y. S HEN: Garaev’s inequality in finite fields not of prime order. Technical
report, Arxiv, 2007. [arXiv:math.NT/0703676]. 2.8
[34] * S. K HOT: Improved inapproximability results for MaxClique, Chromatic Num-
ber and Approximate Graph Coloring. In Proc. 42nd FOCS, pp. 600–609, 2001.
[FOCS:10.1109/SFCS.2001.959936]. 1.1, 7.4
[35] * L. L OVASZ: On the ratio of the optimal integral and fractional covers. Discrete Mathematics,
13:383–390, 1975. 7
[36] * A. L UBOTZKY, R. P HILIPS , AND P. S ARNAK: Ramanujan graphs. Combinatorica, 8:261–277,
1988. [Springer:k285687344657q53]. 2.5
[37] * C. L UND AND M. YANNAKAKIS: On the hardness of approximating minimization problems.
Journal of the ACM, 41:960–981, 1994. [JACM:185675.306789]. 1.1
[38] * G.A. M ARGULIS: Explicit group theoretical constructions of combinatorial schemes and their
application to the design of expanders and superconcentrators. Problems of Information Transmis-
sion, 24:39–46, 1988. 2.5
[39] * M. M ORGENSTERN: Existence and explicit constructions of q + 1 regular Ramanujan graphs
for every prime power q. Journal of Combinatorial Theory, Series B, 62:44–62, 1994. [Else-
vier:10.1006/jctb.1994.1054]. 2.5
[40] * E. M OSSEL AND C. U MANS: On the complexity of approximating the VC dimension. Journal
of Computer and System Sciences, 65:660–671, 2002. [JCSS:10.1016/S0022-0000(02)00022-3].
1.2
[41] * N. N ISAN AND A. TA -S HMA: Extracting randomness: A survey and new constructions. Journal
of Computer and System Sciences, 58:148–173, 1999. [JCSS:10.1006/jcss.1997.1546]. 1.2
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 126
L INEAR D EGREE E XTRACTORS AND I NAPPROXIMABILITY
[42] * N. N ISAN AND D. Z UCKERMAN: Randomness is linear in space. Journal of Computer and
System Sciences, 52(1):43–52, 1996. [JCSS:10.1006/jcss.1996.0004]. 1.6, 1.2
[43] * R. R AZ: Extractors with weak random seeds. In Proc. 37th STOC, pp. 11–20, 2005.
[STOC:1060590.1060593]. 1.3, 3, 3.2, 4, 4, 4.3
[44] * O. R EINGOLD , R. S HALTIEL , AND A. W IGDERSON: Extracting randomness via repeated con-
densing. In Proc. 41st FOCS, pp. 22–31, 2000. [FOCS:10.1109/SFCS.2000.892008]. 1.3, 2.7
[45] * A. S AMORODNITSKY AND L. T REVISAN: A PCP characterization of NP with optimal amor-
tized query complexity. In Proc. 32nd STOC, pp. 191–199, 2000. [STOC:335305.335329]. 6
[46] * R. S HALTIEL: Recent developments in explicit constructions of extractors. Bulletin of the Euro-
pean Association for Theoretical Computer Science, 77:67–95, June 2002. 1.2
[47] * A. TA -S HMA , C. U MANS , AND D. Z UCKERMAN: Lossless condensers, unbalanced expanders,
and extractors. Combinatorica, 27:213–240, 2007. [Springer:y86m43u236782602]. 1.3, 2.7, 2.14
[48] * A. TA -S HMA AND D. Z UCKERMAN: Extractor codes. IEEE Transactions on Information The-
ory, 50:3015–3025, 2004. [IEEE:10.1109/TIT.2004.838377]. 1.1, 1.2
[49] * A. TA -S HMA , D. Z UCKERMAN , AND S. S AFRA: Extractors from Reed-Muller codes. Journal
of Computer and System Sciences, 72:786–812, 2006. [JCSS:10.1016/j.jcss.2005.05.010]. 1.2
[50] * T. TAO AND V. V U: Additive Combinatorics. Cambridge University Press, 2006. 2.8
[51] * C. U MANS: Hardness of approximating Σ2p minimization problems. In Proc. 40th FOCS, pp.
465–474, 1999. [FOCS:10.1109/SFFCS.1999.814619]. 1.2
[52] * A. W IGDERSON AND D. X IAO: A randomness-efficient sampler for matrix-valued functions
and applications. In Proc. 46th FOCS, pp. 397–406, 2005. [FOCS:10.1109/SFCS.2005.8]. 1.3, 4
[53] * A. W IGDERSON AND D. Z UCKERMAN: Expanders that beat the eigenvalue bound: Explicit con-
struction and applications. Combinatorica, 19(1):125–138, 1999. [Springer:wcjlnyjmdxf30b9x].
1.2, 1.3, 5, 5
[54] * D. Z UCKERMAN: Simulating BPP using a general weak random source. Algorithmica, 16:367–
391, 1996. [Algorithmica:kx95d4u1jvyxh882]. 1.1, 1.2, 6
[55] * D. Z UCKERMAN: Randomness-optimal oblivious sampling. Random Structures and Algorithms,
11:345–367, 1997. [Wiley:10.1002/(SICI)1098-2418(199712)11:4¡345::AID-RSA4¿3.0.CO;2-Z].
1.2
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 127
D. Z UCKERMAN
AUTHOR
David Zuckerman [About the author]
Department of Computer Science
University of Texas at Austin
1 University Station C0500
Austin, TX 78712
diz cs utexas edu
http://www.cs.utexas.edu/~diz
ABOUT THE AUTHOR
DAVID Z UCKERMAN received his Ph. D. from U.C. Berkeley in 1991 under the supervision
of Umesh Vazirani. Since 1994 he has been on the faculty of the University of Texas
at Austin. His research interests lie primarily in the role of randomness in computation,
particularly pseudorandomness and its relationship to other topics in complexity theory,
coding theory, and cryptography. His hobbies include dancing and Scrabble.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 103–128 128