Theory of Computing, 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 Max Clique and Chromatic Number to within n^{1−ϵ} are NP-hard. We further derandomize results of Khot (FOCS ’01) and show that for some γ > 0, no quasi-polynomial time algorithm approximates Max Clique or Chromatic Number to within n/2^{(logn)^{1−γ}}, unless NP̃= P̃.

The key to these results is a new construction of dispersers, which are related to randomness 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 log_{2}n + O(1) additional random bits for sources with constant 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 Fellowship 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 papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article 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.

\begin{matrix}c \\ ◯ \end{matrix} 2007 David Zuckerman

D. Zuckerman

times logn 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

Max Clique and Chromatic Number 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 Max Clique. The celebrated PCP Theorem of Arora et al. [3] then implied that it is NP-hard to approximate Max Clique to within n^{c} for some constant c > 0. This ratio was improved in [7, 6] until Håstad, in a breakthrough, showed a hardness ratio of n^{1−ϵ} , for any ϵ > 0 [25]. The catch is that Håstad’s reduction is randomized, so his theorem assumes that NP≠ ZPP. Assuming only NP≠ P, Håstad’s hardness ratio becomes n^{1/2−ϵ} . In this paper we derandomize Håstad’s randomized reduction:

Theorem 1.1. For all ϵ > 0, it is NP-hard to approximate Max Clique to within n^{1−ϵ} .

The inapproximability of Chromatic Number has historically been even harder to prove than Max Clique, because advances have typically occurred through reductions from Max Clique. Lund and Yannakakis were the first to show that it is NP-hard to approximate Chromatic Number to within n^{c} for some constant c > 0 [37]. Other reductions ensued, culminating in Feige and Kilian’s proof of a hardness ratio of n^{1−ϵ} [19]. This uses Håstad’s result, so it assumes that NP≠ ZPP. Assuming only NP≠ P, the best previous hardness ratio explicitly stated appears to be n^{1/7−ϵ} [6]. Previous work likely implied something better, though certainly no better than n^{1/2−ϵ} . In this paper we derandomize Feige and Kilian’s result:

Theorem 1.2. For all ϵ > 0, it is NP-hard to approximate Chromatic Number to within n^{1−ϵ} .

Engebretsen and Holmerin [16] improved the hardness ratios for both problems to n^{1−o(1)} under the stronger assumption that NP⊈ ZPTIME(2^{polylog(n)}). Khot [34] later improved these n^{1−o(1)} factors to n/2^{(logn)^{1−γ}} 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.

Linear Degree Extractors and Inapproximability

Theorem 1.3. For some γ > 0, it is NP̃-hard to approximate Max Clique to within n/2^{(logn)^{1−γ}}.

Theorem 1.4. For some γ > 0, it is NP̃-hard to approximate Chromatic Number to within n/2^{(logn)^{1−γ}}.

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 Max Clique (e.g., [54, 48]), but it was not known for Chromatic Number. 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) = min_{x}{−log_{2}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 additional 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,U_{d}) is ϵ-close in statistical (variation) distance to U_{m}. We say Extis 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 relatively 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 Zuckerman [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 = 2^{d}, 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 = logD. 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 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 Max Clique [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(nlog^{∗}n) for k ≥ \sqrt{n}log^{2}n, but could only output about k/\sqrt{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 = 2^{d} = 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 DISis a (K,s)-disperser if, for any X ⊆ [N] with |X| ≥ K, |Γ(X)| ≥ sM. We say DISis 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/logs^{−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 = 2^{n}]×[D] → [M = 2^{m}] such that D = O(n/logs^{−1} ) and m ≥ (1−α)δn. For subconstant δ = δ(n), the dependence is D = (1/δ)^{O(1)}n/logs^{−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 algorithms without using many additional random bits [1, 29, 13]. This yields a disperser for sources with entropy 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 𝔽_{q}, where q = 2^{p}. This bipartite graph has as independent sets the lines and points in the plane 𝔽_{q}^{2}, with an edge between a point and a line if the point lies on the line. View the input distribution as a distribution over the q^{3} 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 δ′> δ. 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 improvement 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 applications 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 𝔽_{q} 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 𝔽_{q}, then AB+C is close to a rate-(1+α′)δ-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 disperser 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 = 2^{k}. 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 2^{polylog(n)}. NP̃and P̃are the quasi-polynomial analogues of NPand P, respectively. As usual with inapproximability results, we analyze the appropriate gap problem.

Note that no language is NP̃-complete with respect to polynomial-time reductions. For if there were such a language, it would be in TIME(2^{(logn)^{c}}) for some c; but then NP̃⊆ TIME(2^{(logn)^{c+1}} ), 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 X_{1} and X_{2} be two distributions on the same space Ω. The statistical, or variation, distance between them is

∥X_{1}− X_{2}∥ = max_{S⊆Ω}|X_{1}(S) − X_{2}(S)| = \frac{1}{2} ∑_{s∈Ω} |X_{1}(s) − X_{2}(s)|.

We say X_{1} and X_{2} are ϵ-close if ∥X_{1} − X_{2}∥ ≤ ϵ, and are ϵ-far otherwise. We say a distribution on {0,1}^{n} is ϵ-uniform if it is ϵ-close to U_{n}, 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 logN + logD 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 logN + logD. 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).

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,s′)-disperser DIS_{1} : [N]×[D_{1}] → [N′] and an efficient (K′= s′N′,s)- disperser DIS_{2} : [N′] × [D_{2}] → [M], we can build an efficient (K,s)-disperser DIS: [N] × [D_{1}D_{2}] → [M]. If moreover DIS_{2} is a strong (K′,s)-disperser, then DISis a strong (K,s/D_{1})-disperser.

Proof. Take DIS(x,y_{1}∘ y_{2}) = DIS_{2}(DIS_{1}(x,y_{1}),y_{2}). It is straightforward to verify that DIS is a (K,s)- disperser. To see the final statement of the lemma, suppose DIS_{2} is strong. Then DIS(x,y_{1}∘ y_{2}) ∘ y_{2} is a (K,s)-disperser, so DIS(x,y_{1}∘ y_{2}) ∘ y_{1}∘ y_{2} is a (K,s/D_{1})-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 DIShas 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 2^{c}-regular 2^{−γc}-expanders on 2^{m} nodes, for a constant γ > 0.

Extending earlier constructions which required large primes [36, 38], Morgenstern [39] gave explicit constructions which achieve this with γ approaching 1/2. However, because the number of vertices is not 2^{m} and there are restrictions on the degree, it is easier to use expanders by Gabber and Galil [20]. They gave an explicit construction of 8-regular λ-expanders on 2^{m} nodes, for even m, where λ = 5\sqrt{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 operations. By taking the (c/3)th power of the graph, we get a 2^{c}-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 (X_{1},...,X_{ℓ}), such that some X_{i} 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 X_{i}. Further note that in a somewhere-k-source which is not elementary, all X_{i} may have low min-entropy.

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 ksource X, C(X,U_{d}) 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 ⟨C(X,y)⟩_{y∈{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 (2^{k},(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 Z_{1} is ϵ_{1}-close to an ℓ_{1}-source, and for all z_{1} ∈ supp(Z_{1}), the distribution (Z_{2} | Z_{1} = z_{1}) is ϵ_{2}-close to an ℓ_{2}-source. Then Z_{1}∘ Z_{2} is ϵ_{1}+ ϵ_{2}-close to an ℓ_{1}+ ℓ_{2}-source.

Proof. Let W_{1} be an arbitrary ℓ_{1}-source which is ϵ_{1}-close to Z_{1}. For w_{1} ∈ supp(Z_{1}) ∩ supp(W_{1}), define the distribution of (W_{2} | W_{1} = w_{1}) to be an arbitrary ℓ_{2}-source which is ϵ_{2}-close to (Z_{2} | Z_{1} = w_{1}). For w_{1} ∈ supp(W_{1}) \ supp(Z_{1}), define the distribution of (W_{2} | W_{1} = w_{1}) to be the uniform distribution. Then W_{1}∘ W_{2} is an ℓ_{1}+ ℓ_{2}-source, which is ϵ_{1}+ ϵ_{2}-close to Z_{1}∘ Z_{2},

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.

Lemma 2.14 ([47]). Suppose that C : {0,1}^{n}× {0,1}^{d_{1}} → {0,1}^{n′} is an efficient (strong) (k → ℓ,ϵ_{1})- condenser, and Ext: {0,1}^{n′}× {0,1}^{d_{2}} → {0,1}^{m} is an efficient (strong) (ℓ,ϵ_{2})-extractor. Then

Ext′(x,y_{1}∘ y_{2}) = Ext(C(x,y_{1}),y_{2})

is an efficient (strong) (k,ϵ_{1}+ ϵ_{2})-extractor.

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 = 𝔽_{q} 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 randomness we need rate close to 1.

Proposition 3.1. For any α > 0, there is a β,c_{0} > 0 such that for any c = c(n) ≥ c_{0}, there is an efficient family of strong (K = N^{1−β} ,2^{−c})-dispersers DIS: [N = 2^{n}] × [D] → [M = 2^{m}] such that D ≤ αn/c and m ≥ (1 − α)n. (Let γ > 0 be the constant from Section 2.5. We can take c_{0} = 2/γ and β = αγ/5.)

Proof. We use the disperser of [1]. Set s = 2^{−c}, and m = (1−α)n. Let G be a 2^{c}-regular 2^{−γc}-expander on [2^{m}] (see Section 2.5). To find the neighbors of a vertex u ∈ [2^{n}], use the n bits defining u to choose a random vertex v_{0} ∈ [2^{m}] and then take a random walk v_{1},...,v_{D} on G. Connect u to v_{1},...,v_{D}. We ignore v_{0} 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 ⊆ [2^{m}] and s = |S|/2^{m}, Kahale showed that

Pr[(∀i)v_{i} ∈ 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 S_{i}, |S_{i}| = s_{i}2^{m}, where the average of the s_{i} is at most s. By the result of Kahale given as Theorem A.5 in [22], for a uniformly random walk

Pr[(∀i)v_{i} ∈ S_{i}]≤ \sqrt{s_{1}s_{D}} ∏_{i=2}^{D} \sqrt{s_{i}+ (1 − s_{i})λ^{2}} ≤ \sqrt{∏_{i=1}^{D} (λ^{2}+ (1 − λ^{2})s_{i})}

≤ ( \frac{1}{D} ∑_{i=1}^{D} (λ^{2}+ (1 − λ^{2})s_{i})) ^{D/2} ≤ (λ^{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 = 2^{n}]×[D] → [M = 2^{m}] 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. However, 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

Corllary 3.4. For any β,δ > 0, there is an efficient family of strong (K = N^{δ},M^{−β} )-dispersers DIS: [N = 2^{n}] × [D] → [M = 2^{m}] 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 = 2^{n}]×[D] → [M = 2^{m}] such that D = O(n/logs^{−1} ) and m = Ω(n). For subconstant δ = δ(n) the dependence is D = (1/δ)^{O(1)}n/logs^{−1} and m = δ^{O(1)}n.

Proof. Let DIS_{1} : [N = 2^{n}]×[D_{1} = O(1)] → [N′= 2^{n′}] be an efficient strong (K = N^{δ},(N′)^{−.1} )-disperser from Corollary 3.4, with n′= Ω(n). Let DIS_{2} : [N′] × [D_{2} ≤ n′/lgs^{−1} ] → [M = 2^{m}], be an efficient strong (K′= (N′)^{.9},s)-disperser given by Proposition 3.1, with m = n′/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.

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 = 2^{d} ≤ αn.

Proof. Set m = (1 − α)n and c = 3 (say). Let G be a 2^{c}-regular λ-expander on [2^{m}] with λ bounded away from 1 (see Section 2.5). To find the neighbors of a vertex u ∈ [2^{n}], use the n bits defining u to choose a random vertex v_{0} ∈ [2^{m}] and then take a random walk v_{1},...,v_{D} on G. Connect u to v_{1},...,v_{D}. As before, n = m + Dc, and D = (n − m)/c = αn/c.

Let S ⊆ [2^{m}] have density μ = |S|/2^{m}. First consider when the bits describing the random walk are chosen uniformly, and let the random variable μ̂ denote the fraction of v_{i} 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[|μ̂− μ| ≥ ϵ] ≤ 2exp(−(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 = 2^{d} ≤ αn.

Proof. We use the same construction. For the proof, we must now show near uniformity over [D]×[2^{m}]. We therefore consider S ⊆ [D] × [2^{m}], so S = ∪_{i}{i} × S_{i}. Again consider when the bits describing the random walk are chosen uniformly, and now let the random variable μ̂ denote the fraction of v_{i} which are in S_{i}. Wigderson and Xiao [52] improved Gillman’s theorem above for this case. We again use Healy’s improved constants [27]):

Pr[|μ̂− μ| ≥ ϵ] ≤ 2exp(−(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 Theorem 3.2. For extractors, we need to use the improved strong condenser due to Raz [43].

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 = 2^{d} = 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 Θ(n^{2}), 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)} ) somewherecondenser C_{1} : {0,1}^{n}× {0,1}^{d_{1}} → {0,1}^{m_{1}}, where d_{1} = O(1) and m_{1} = Ω(n). By the main theorem of [15], there is a “strong merger” M : ({0,1}^{m_{1}})^{2^{d_{1}}} × {0,1}^{d} → {0,1}^{m} with d = f(d_{1}) = O(1) and m = Ω(m_{1}) such that whenever the input X_{1} on ({0,1}^{m_{1}})^{2^{d_{1}}} is a somewhere rate (1−δ/2)-source, then the average over y ∈ {0,1}^{d} of the distance of M(X_{1},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(⟨C_{1}(x,y_{1}⟩_{y_{1}∈{0,1}^{d_{1}}},y).

The following lemma is the condenser analogue to the corresponding extractor lemma in [53].

Lemma 5.3. Suppose that C_{1} : {0,1}^{n}× {0,1}^{d_{1}} → {0,1}^{m_{1}} is a strong (k → ℓ_{1},ϵ_{1})-condenser and C_{2} : {0,1}^{n} × {0,1}^{d_{2}} → {0,1}^{m_{2}} is a strong (k − m_{1} − s → ℓ_{2},ϵ_{2})-condenser. Then C : {0,1}^{n} × {0,1}^{d_{1}+d_{2}} → {0,1}^{m_{1}+m_{2}}, given by

C(x,y_{1}∘ y_{2}) = C_{1}(x,y_{1}) ∘ C_{2}(x,y_{2}),

is a strong (k → ℓ_{1}+ ℓ_{2},ϵ_{1}+ ϵ_{2}+ 2^{−s})-condenser.

Proof. Let X be a k-source. For y ∈ {0,1}^{d_{i}}, let ϵ_{i}^{y} denote the minimum distance of C_{i}(X,y) to some ℓ_{i}-source. Fix y_{1} ∈ {0,1}^{d_{1}}. Let S denote the set of low-probability elements in the output:

S = {z | Pr_{X}[C_{1}(X,y_{1}) = z] ≤ 2^{−(m_{1}+s)} }.

Then Pr[C_{1}(X,y_{1}) ∈ S] ≤ |S|2^{−(m_{1}+s)} ≤ 2^{−s}. For z ∉ S, X conditioned on C_{1}(X,y_{1}) = z is a (k −m_{1}−s)- source. Hence, under such conditioning, for each y_{2} ∈ {0,1}^{d_{2}}, C_{2}(X,y_{2}) is within ϵ_{2}^{y_{2}} of some ℓ_{2}-source. Putting this together as in Lemma 2.13, C(X,y_{1} ∘ y_{2}) is within ϵ_{1}^{y_{1}}+ 2^{−s} + ϵ_{2}^{y_{2}} of some ℓ_{1} + ℓ_{2}-source. Since the average of ϵ_{i}^{y_{i}} 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 C′: {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 C′= C. Now assume the lemma for a given t. Set C_{1} to be the condenser given by the lemma for t, and set C_{2} = 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 − β),ϵ′)-condenser C : {0,1}^{n}× {0,1}^{d} → {0,1}^{m}, where ϵ′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ϵ′+ 2^{−s})-condenser C′: {0,1}^{n}× {0,1}^{id} → {0,1}^{tm}. Choosing s = γn and ϵ′small enough so tϵ′+ 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 = 2^{d} = 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 = 2^{n}]×[D] → [M = 2^{m}] such that D = O(n/logs^{−1} ) and m ≥ (1−α)δn. For subconstant δ = δ(n), the dependence is D = (1/δ)^{O(1)}n/logs^{−1} and m = δ^{O(1)}n.

6 Max Clique

In this section, we show how our dispersers yield inapproximability results for Max Clique. We assume some familiarity with PCPs. Since the inapproximability of Max Clique follows from the proof of the inapproximability of Chromatic Number, 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 Max Clique 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. FPCP_{s}(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⊆ FPCP_{s}(r,f), then it is NP-hard to distinguish whether a graph on 2^{r+f} vertices has clique number at least 2^{r} or at most s2^{r}.

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⊆ FPCP_{2^{−ℓ}}(O(logn),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⊆ FPCP_{s}(r,f) and there is a polynomial-time constructible (K,s)-disperser DIS: [2^{R}] × [D] → [2^{r}]. Then NP⊆ FPCP_{K/2^{R}}(R,Df), and hence it is NP-hard to distinguish whether a graph on 2^{R+Df} vertices has clique number at least 2^{R} or clique number at most K.

This suffices to prove our theorem. Theorem 1.1. It is NP-hard to approximate Max Clique to within n^{1−ϵ} for any ϵ > 0.

Proof. Equivalently, we will show a factor of n^{1−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(logN)/logs^{−1} , for some c = c(ϵ). Let f̄≤ ϵ/c, and apply Theorem 6.3 to get an ℓ and r = r(n) = O(logn) such that NP⊆ FPCP_{2^{−ℓ}}(r,f̄ℓ). Now let s = 2^{−ℓ}, so there is an efficient (K = (2^{R})^{ϵ},2^{−ℓ})-disperser DIS: [2^{R}] × [D] → [2^{r}]. Apply Lemma 6.4 with this disperser, and note that Df ≤ (cR/ℓ) · (ℓf̄) = f̄· cR ≤ ϵR. Hence it is NP-hard to distinguish clique number at least 2^{R} 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(logn), so the reduction is polynomial time.

To obtain inapproximability up to an n^{1−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.

Theorem 6.5 ([26]). For any ℓ = ℓ(n) which is one less than a perfect square,

NP⊆ FPCP_{2^{−ℓ}}(O(ℓlogn),2\sqrt{ℓ + 1}).

We can now prove: Theorem 1.3. For some γ > 0, it is NP̃-hard to approximate Max Clique to within n/2^{(logn)^{1−γ}}.

Proof. Set ϵ = ϵ(n) = 1/logn. 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 degree D ≤ (logn)^{c}(logN)/logs^{−1} . Let ℓ = 9(logn)^{2(c+1)} and s = 2^{−ℓ}. Apply Theorem 6.5 to get r = r(n) = polylog(n) such that NP⊆ FPCP_{s}(r,3\sqrt{ℓ}). We’ll use the polynomial-time constructible (K = (2^{R})^{ϵ},2^{−ℓ})-disperser DIS: [2^{R}] × [D] → [2^{r}]. Apply Lemma 6.4 with disperser DIS, and note that Df ≤ (R(logn)^{c}/ℓ) · (3\sqrt{ℓ}) = R/logn = ϵR. Hence it is NP-hard to distinguishing clique number at least 2^{R} from clique number at most 2^{R/logn} in graphs on 2^{(1+1/logn)R} vertices. Since R = polylog(n), the theorem follows.

7 Chromatic Number

Now we show how our dispersers imply the NP-hardness of approximating Chromatic Number to within n^{1−ϵ} for any ϵ > 0. We derandomize Feige’s and Kilian’s proof [19] of the same inapproximability ratio but under the stronger assumption that NPis 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 number χ [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 c′< c. They actually need c′= 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 ∉ 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) ≤ 2^{3γℓ+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 G′of the product graph G^{D} which has hardness ratio |V (G′)|^{1−ϵ} . G^{D} is defined with respect to the following “OR” graph product.

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),(v′,w′)} where {v,v′} ∈ E or {w,w′} ∈ F.

Note that (v_{1},...,v_{D}) is adjacent to (w_{1},...,w_{D}) in G^{D} if any (v_{i},w_{i}) is an edge in G. It is straightforward 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} (G′) ≤ χ_{f} (G^{D}) = χ_{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(G^{D}) to be the induced subgraph of G^{D} on vertex set DIS(X).

Lemma 7.3. Given a graph G = (V,E) and a disperser DISwith degree D, let G′= (V′,E′) = DIS(G^{D}). Then

1. χ_{f} (G′) ≤ (χ_{f} (G))^{D}.

2. If α(G) < s|V | and DISis a strong (K,s)-disperser, then α(G′) < K, and hence χ_{f} (G′) > |V′|/K.

Proof. The first part follows because χ_{f} (G′) ≤ χ_{f} (G^{D}) = (χ_{f} (G))^{D}. For the second part, suppose α(G′) ≥ K, and let X be an independent set in G′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 {v_{i},w_{i}}. If v_{i} is the ith coordinate of v, and w_{i} is the ith coordinate of w, then because we are using the OR graph product, {v,w} is an edge in G′. 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 Chromatic Number to within n^{1−ϵ} 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/logs^{−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 G′on N vertices such that if x ∈ L,

χ_{f} (G′) ≤ s^{−γD} ≤ 2^{γcn}= N^{ϵ}.

If x ∉ L, then α(G′) ≤ N^{ϵ}, so χ_{f} (G′) ≥ 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:

Theorem 7.4 ([34]). For any β > 0, there is a quasi-polynomial-time reduction from an NP-complete language L to Chromatic Number with the following properties. On input x of size n, the algorithm outputs a graph G = (V,E) such that

1. |V | ≤ 2^{(logn)^{1+3β}} ;

2. If x ∈ L then χ_{f} (G) ≤ 2^{(logn)^{β}};

3. If x ∉ L then α(G) < 2^{−(logn)^{2β}} |V |.

We can now show: Theorem 1.4. For some γ > 0, it is NP̃-hard to approximate Chromatic Number to within n/2^{(logn)^{1−γ}}.

Proof. We use the polynomial-time constructible (N^{δ},s)-strong disperser from Theorem 1.9, with s = 2^{−(logn)^{2β}} and δ to be chosen shortly. This has degree D ≤ (logN)/(δ^{c}(logn)^{2β}). Set δ = (logn)^{−β/2c} . Applying Lemma 7.3, it is NP̃-hard to distinguish between graphs on N vertices with chromatic number N^{δ} from those with chromatic number 2^{(logn)^{β}D}≤ N^{(logn)^{−β/2}} .

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 = 𝔽_{q}, 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 ≤ p^{1.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 = 𝔽_{q}, 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, 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 = (X_{1},...,X_{ℓ}) is ϵ-close to somewhere-k-light if the probability, when (x_{1},...,x_{ℓ}) is output according to X, that no x_{i} are light is at most ϵ. We say x_{i} is light if Pr[X_{i} = x_{i}] ≤ 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 = (X_{1},...,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 (x_{1},...,x_{ℓ}) where x_{i} 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 ≠ 0 with probability at least 2^{−t} (since ℓ2^{−t} < 1 − ϵ there is at least one such bin). For any (x_{1},...,x_{ℓ}) in bin i,

Pr[X_{i} = x_{i} | bin(X) = i] ≤ Pr[X_{i} = x_{i}]/Pr[bin(X) = i] ≤ 2^{t}· 2^{−k} .

Hence, if we let Y^{i} denote the distribution of X conditional on bin(X) = i, we get that Y_{i}^{i} 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 | < 2^{k+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.

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 = 2^{k} = q^{3δ}, and set k′= (1 + α/2)(2k/3). Suppose the output (X,Y) of h is not ϵ-close to a somewhere-k′-source. Let P = S and L = T be the sets of size less than K_{0} = 2^{k′+1}/ϵ given by Lemma 8.6. Assuming without loss of generality that α ≤ .1, note that K_{0} ≤ q^{2δ}1 + α/2 ≤ q^{1.8·1.05}< q^{1.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,

I(P,L) = O(K_{0}^{3/2−α} ) = 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 = 𝔽_{q}, 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| < 2^{k}, such that Pr[X ∈ S] ≥ ϵ.

Proof. Take S = {s | X(s) > 2^{−k}}, so |S| < 2^{k}. 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 ksource. Suppose AB + C is ϵ-far from a k′ source, where k′= (1 + α)k. Let S be the set of size less than K′= 2^{k′}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 = 2^{k} ≤ |F |^{.9}. On the other hand, since |L| = K^{2} ≤ |F |^{1.8} and |P| ≤ K · K′= 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: 𝔽_{q}×𝔽_{q} → 𝔽_{q} 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 = A^{2}, 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 = 𝔽_{q}, 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}.

1Bourgain’s proof also uses the Incidence Theorem 8.2, but it was done independently of our use of the Incidence Theorem 8.2 in Subsections 8.1 and 8.2.

Theory of Computing, Volume 3 (2007), pp. 103–128 122

Then |T | ≥ \frac{ϵ}{2}|B| ≥ \frac{ϵ}{2}q^{δ}. Fix y′∈ T. Let Z be distributed as X, but independent of X and Y. Then

Pr_{X,Y,Z}[g(X,Y) = g(Z,y′)] > Pr_{Z}[g(Z,y′) ∈ S]q^{−(δ+β)} ≥ \frac{ϵ}{2}q^{−(δ+β)} .

Let X_{1} also be distributed as X, but independent of all previously defined random variables. We now show that a function in both X, X_{1}, and Y, which is linear in Y, still has significant probability of being in S. This will give us many more lines.

Pr_{X,X_{1},Z,Y}[X(X + \frac{X_{1}}{Z}(X_{1}+ Y) − Z) ∈ S] ≥ ∑_{y′∈T}Pr[X(X + y′) ∈ S]Pr[\frac{X_{1}}{Z}(X_{1}+ Y) − Z = y′]
= ∑_{y′∈T}Pr[X(X + y′) ∈ S]Pr[X_{1}(X_{1}+ Y) = Z(Z + y′)]

> |T |\frac{ϵ}{2} · \frac{ϵ}{2}q^{−(δ+β)} > \frac{ϵ^{3}}{8}q^{−β} .

Therefore, there is a fixed z such that

Pr_{X,X_{1},Y}[X(X + \frac{X_{1}}{z}(X_{1}+ Y) − z) ∈ S] > \frac{ϵ^{3}}{8}q^{−β} .  (8.1)

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,x_{1}}(y) denote the line

\frac{xx_{1}}{z}y + (x^{2}+ \frac{xx_{1}^{2}}{z}− zx),

and let L denote the set of all such lines as x,x_{1} range over A.

Of course, |L| ≤ |A|^{2} = q^{2δ}. We also show |L| ≥ q^{2δ}/3 by observing that, for fixed z,w, there are at most 3 nonzero solutions in x,x_{1} to

z = \frac{xx_{1}}{z}
w = x^{2}+ \frac{xx_{1}^{2}}{z}− zx.

We define the points P = B × S, so |P| < q^{2δ+β} . By Equation (8.1) and the fact that the pairs (x,x_{1}) overcount lines by at most a factor of 3, the number of incidences is at least \frac{ϵ^{3}}{24}q^{3δ−β} . 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.

References

[1] * M. Ajtai, J. Komlós, and E. Szemerédi: Deterministic simulation in LOGSPACE. In Proc. 19th STOC, pp. 132–140, 1987. [STOC:28395.28410]. 1.3, 3

[2] * N. Alon, U. Feige, A. Wigderson, and D. Zuckerman: Derandomized graph products. Computational Complexity, 5:60–75, 1995. [Springer:r591795p150lj86q]. 7

[3] * S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy: Proof verification and the hardness of approximation problems. Journal of the ACM, 45:501–555, 1998. [JACM:278298.278306]. 1.1

[4] * B. Barak, R. Impagliazzo, and A. Wigderson: Extracting randomness using few independent sources. In Proc. 45th FOCS, pp. 384–393, 2004. [FOCS:10.1109/FOCS.2004.29]. 1.3, 8, 8.2

[5] * B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson: 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. Bellare, O. Goldreich, and M. Sudan: Free bits, PCPs, and nonapproximability — 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. Bellare and M. Sudan: Improved non-approximability results. In Proc. 26th STOC, pp. 184–193, 1994. [STOC:195058.195129]. 1.1

[8] * R. Boppana and M. Halldorsson: Approximating maximum independent sets by excluding subgraphs. Bit, 32:180–196, 1992. 1.1

[9] * J. Bourgain: More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1–32, 2005. [WorldSci:10.1142/S1793042105000108]. 1.3, 8, 8.3

[10] * J. Bourgain, A. Glibichuk, 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. Bourgain, N. Katz, 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. Chor and O. Goldreich: 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

[13] * A. Cohen and A. Wigderson: Dispersers, deterministic amplification, and weak random sources. In Proc.30th FOCS, pp. 14–19, 1989. 1.3

[14] * I.H. Dinwoodie: 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. Raz: Analyzing linear mergers. Technical Report TR05-025, Electronic Colloquium on Computational Complexity, 2005. [ECCC:TR05-025]. 5, 5

[16] * L. Engebretsen and J. Holmerin: Towards optimal lower bounds for clique and chromatic number. Theoretical Computer Science, 299:537–584, 2003. [TCS:10.1016/S0304-3975(02)00535-2]. 1.1

[17] * U. Feige: Randomized graph products, chromatic numbers, and the Lovasz θ function. Combinatorica, 17:79–90, 1997. [Springer:x785787h43724566]. 7

[18] * U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy: 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. Feige and J. Kilian: 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. Gabber and Z. Galil: 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. Gillman: 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. Goldreich: A sample of samplers – a computational perspective on sampling (survey). Technical Report TR97-020, Electronic Colloquium on Computational Complexity, 1997. [ECCC:TR97-020]. 3

[23] * B. Green: Sum-product estimates. Unpublished lecture notes. Available at author’s website, 2005. 2.8

[24] * M. Halldorsson: A still better performance guarantee for approximate graph coloring. Information 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 n^{1−ϵ} . Acta Mathematica, 182:105–142, 1999.

[Springer:m68h3576646ll648]. 1.1, 6, 6.3

[26] * J. Hastad and S. Khot: 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. Healy: Randomness-efficient sampling within NC^{1}. In Proc. 10th Intern. Workshop on Randomization and Computation (RANDOM), pp. 398–409, 2006. [Springer:b773545612310728]. 4, 4

[28] * S. Hoory, N. Linial, and A. Wigderson: Expander graphs and their applications. Bulletin of the American Mathematical Society, 43:439–561, 2006. 2.5

[29] * R. Impagliazzo and D. Zuckerman: How to recycle random bits. In Proc.30th FOCS, pp. 248–253, 1989. 1.3

[30] * N. Kahale: Eigenvalues and expansion of regular graphs. Journal of the ACM, 42:1091–1106, 1995. [JACM:210118.210136]. 3

[31] * N. Kahale: Large deviation bounds for Markov chains. Combinatorics, Probability, and Computing, 6:465–474, 1997. [Cambridge:10.1017/S0963548397003209]. 1.3, 4

[32] * R. M. Karp: Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pp. 85–103. Plenum Press, New York, 1972. 1.1

[33] * N. Katz and C.-Y. Shen: Garaev’s inequality in finite fields not of prime order. Technical report, Arxiv, 2007. [arXiv:math.NT/0703676]. 2.8

[34] * S. Khot: Improved inapproximability results for MaxClique, Chromatic Number and Approximate Graph Coloring. In Proc. 42nd FOCS, pp. 600–609, 2001. [FOCS:10.1109/SFCS.2001.959936]. 1.1, 7.4

[35] * L. Lovasz: On the ratio of the optimal integral and fractional covers. Discrete Mathematics, 13:383–390, 1975. 7

[36] * A. Lubotzky, R. Philips, and P. Sarnak: Ramanujan graphs. Combinatorica, 8:261–277, 1988. [Springer:k285687344657q53]. 2.5

[37] * C. Lund 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. Margulis: Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators. Problems of Information Transmission, 24:39–46, 1988. 2.5 [39] * M. Morgenstern: 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. [Elsevier:10.1006/jctb.1994.1054]. 2.5

[40] * E. Mossel and C. Umans: 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. Nisan and A. Ta-Shma: 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

[42] * N. Nisan and D. Zuckerman: 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. Raz: 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. Reingold, R. Shaltiel, and A. Wigderson: Extracting randomness via repeated condensing. In Proc. 41st FOCS, pp. 22–31, 2000. [FOCS:10.1109/SFCS.2000.892008]. 1.3, 2.7

[45] * A. Samorodnitsky and L. Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199, 2000. [STOC:335305.335329]. 6

[46] * R. Shaltiel: Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science, 77:67–95, June 2002. 1.2

[47] * A. Ta-Shma, C. Umans, and D. Zuckerman: Lossless condensers, unbalanced expanders, and extractors. Combinatorica, 27:213–240, 2007. [Springer:y86m43u236782602]. 1.3, 2.7, 2.14

[48] * A. Ta-Shma and D. Zuckerman: Extractor codes. IEEE Transactions on Information Theory, 50:3015–3025, 2004. [IEEE:10.1109/TIT.2004.838377]. 1.1, 1.2

[49] * A. Ta-Shma, D. Zuckerman, and S. Safra: 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. Vu: Additive Combinatorics. Cambridge University Press, 2006. 2.8

[51] * C. Umans: Hardness of approximating Σ_{2}^{p} minimization problems. In Proc. 40th FOCS, pp. 465–474, 1999. [FOCS:10.1109/SFFCS.1999.814619]. 1.2

[52] * A. Wigderson and D. Xiao: 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. Wigderson and D. Zuckerman: Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125–138, 1999. [Springer:wcjlnyjmdxf30b9x]. 1.2, 1.3, 5, 5 [54] * D. Zuckerman: Simulating BPP using a general weak random source. Algorithmica, 16:367–

391, 1996. [Algorithmica:kx95d4u1jvyxh882]. 1.1, 1.2, 6

[55] * D. Zuckerman: 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

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 Zuckerman 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.