Extractors and pseudorandom generators.
We introduce a new approach to constructing extractors. Extractors are algorithms that transform a &quote;weakly random&quote; distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, and tend to be very difficult to obtain.We demonstrate an unsuspected connection between extractors and pseudorandom generators. In fact, we show that every pseudorandom generator of a certain kind is an extractor.A pseudorandom generator construction due to Impagliazzo and Wigderson, once reinterpreted via our connection, is already an extractor that beats most known constructions and solves an important open question. We also show that, using the simpler Nisan--Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are simple and admit a short self-contained description.
Introduction
An extractor is an algorithm that converts a \weak source of randomness" into an almost uniform
distribution by using a small number of additional truly random bits. Extractors have several
important applications (see e.g. [Nis96]). In this paper we show that pseudorandom generator
constructions of a certain kind are extractors. Using our connection and some new ideas we describe
constructions of extractors that improve most previously known constructions and that are simpler
than previous ones.
1.1 Denitions
We now give the formal denition of an extractor and state some previous results. We rst need
to dene the notions of min-entropy and statistical dierence.
We say that (the distribution of) a random variable X of range f0; 1g n has min-entropy at least
k if for every x 2 f0; 1g n it holds is an integer, then a canonical example of
a distribution having min-entropy k is the uniform distribution over a set S  f0; 1g n of cardinality
Indeed, it is implicit in [CG88] that if a distribution has min-entropy k then it is a convex
combination of distributions each one of which is uniform over a set of size 2 k . We will consider
distributions of min-entropy k as the formalization of the notion of weak sources of randomness
containing k \hidden" bits of randomness. In the rest of this paper we will often call (n; k)-source a
An extended abstract of this paper is to appear in the Proceedings of the 31st ACM Symposium on Theory of
Computing [Tre99].
y luca@cs.columbia.edu. Computer Science Department, Columbia University.
random variable X ranging over f0; 1g n and having min-entropy at least k. The use of min-entropy
to measure \hidden randomness" has been advocated by Chor and Goldreich [CG88] and, in full
generality, by Zuckerman [Zuc90]. The statistical dierence between two random variables X and
Y with range f0; 1g n is dened as
and we say that X and Y are "-close if jjX Y jj  ". For an integer l we denote by U l a random
variable that is uniform over f0; 1g l .
A function Ext : f0; 1g n  f0; 1g t ! f0; 1g m is a (k; ")-extractor if for every random variable
X of min entropy at least k it holds that Ext(X; U t ) is "-close to the uniform distribution over
. A weaker kind of combinatorial construction has also been considered: A function Disp :
is a (k; ")-disperser if for every subset S  f0; 1g m such that jSj > "2 m
and for every X of min-entropy k it holds Pr[Disp(X; U t
One would like to have, for every n and k, constructions where t is very small and m is as close
to k as possible. There are some limitations towards this goal: One can show that, if k < n 1
and " < 1=2, then it must be the case that t
it must be the case that m  It is possible to show (non-
constructively) that for every n; k; ", there is a (k; ")-extractor
It is an open question to match such
bounds with polynomial-time computable functions Ext.
1.2 Previous Work and Applications
The natural application of extractors is to allow the simulation of randomized algorithms even in
(realistic) settings where only weak sources of randomness are available. This line of research has a
long history, that dates back at least to von Neumann's algorithm for generating a sequence of unbiased
bits from a source of biased but identically distributed and independent bits [vN51]. More
recent work by Santha and Vazirani [SV86] and Vazirani and Vazirani [VV85] considered much
weaker sources of randomness (that they call \slightly random" sources) that are still su-cient to
allow simulations of arbitrary randomized algorithms. These results were generalized by Chor and
Goldreich [CG88] and Cohen and Wigderson [CW89], and nally by Zuckerman [Zuc90], who introduced
the current denition (based on min-entropy) of weak random sources and a construction
of extractors (although the term extractor was coined later, in [NZ93]). The main question about
simulation of randomized algorithms using weak random sources can be stated as follows: suppose
that for every n we have access to a (n; k(n))-source, and that we are given a polynomial-time
randomized algorithm that we want to simulate given only one access to one of the sources: what
is the most slowly growing function k() such that we can have a polynomial-time simulations? For
a \black-box" simulation, where the randomized algorithm is given as an oracle, it is impossible to
solve the simulation problem in polynomial time with a family of (n; n o(1) )-sources. The best one
can hope to achieve is to have, for every - > 0, a simulation that works in polynomial time given
a (n; n -source. We will call such a simulation an entropy-rate optimal simulation. Improved constructions
of extractors appeared in [NZ93, SZ94, TS96, Zuc96b], but none of these constructions
implies an entropy-rate optimal simulation of randomized algorithms. Dispersers are objects similar
to, but less powerful than, extractors. Randomized algorithms having one-sided error probability
can be simulated by using weak random sources and dispersers. Saks et al. [SSZ98] give a construction
of dispersers that implies an entropy-rate optimal simulation of one-sided error randomized
Reference Min entropy k Output length m Additional randomness t Type
[GW97] n a n (a) O(a) Extractor
log    log n) Extractor
poly log n
This paper
any k

Table

1: Parameters in previous constructions and our construction of (k; ") extractors Ext :
. In the expressions, " is xed and arbitrarily small, and  > 0 is an
arbitrarily small constant. O() notations hide dependencies on " and .
algorithms with weak random sources. Andreev et al. [ACRT99] show how to use the dispersers
of Saks et al. in order to give entropy-rate optimal simulations of general randomized algorithms
using weak random sources. The result of Andreev et al. leaves open the question of whether there
exists a construction of extractors that is good enough to imply directly such entropy-rate optimal
simulations.
Extractors are also used to derandomize randomized space-bounded computations [NZ93] and
for randomness-e-cient reduction of error in randomized algorithms (see [Zuc96b, GZ97] and references
therein). They yield oblivious samplers (as dened in [BR94]), that have applications to
interactive proofs (see [Zuc96b] and references therein). They also yield expander graphs, as discovered
by Wigderson and Zuckerman [WZ93], that in turn have applications to superconcentrators,
sorting in rounds, and routing in optical networks. Constructions of expanders via constructions of
extractors and the Wigderson-Zuckerman connection appeared in [NZ93, SZ94, TS96], among oth-
ers. Extractors can also be used to give simple proofs of certain complexity-theoretic results [GZ97],
and to prove certain hardness of approximation results [Zuc96a]. An excellent introduction to extractors
and their applications is given by a recent survey by Nisan [Nis96] (see also [NTS98], and
[Gol99] for a broader perspective).
In

Table

1 we summarize the parameters of the previous best constructions, and we state two
special cases of the parameters arising in our construction.
1.3 Our Result
The extractors constructed in this paper work for any min-entropy
43 , extract a slightly
sub-linear fraction of the original randomness (i.e. the length of the output is for an
arbitrarily small  > 0) and use O(log n) bits of true randomness. In fact, a more general result
holds, as formalized below.
Theorem 1 (Main) There is an algorithm that on input parameters n,
where

(log
log(k=2m)  e
log(k=2m)
In particular, for any xed constants " > 0 and 0 <
< 1 we have for every n an explicit
polynomial-time construction of an (n
It should be noted that the running time of our extractor is exponential in the parameter t
(additional randomness), and so the running time is super-polynomial when the additional randomness
is super-logarithmic. However, the 2 t factors in the running time of the extractor is payed
only once, to construct a combinatorial object (a \design") used by the extractor. After the design
is computed, each evaluation of the extractor can be implemented in linear time plus the time that
it takes to compute an error-correcting encoding of the input of the extractor. It is possible to
generate designs more e-ciently, and so to have a polynomial-time extractor construction for every
min-entropy. We omit the details of such construction, since the construction of \weak designs" in
[RRV99] (see below) give better extractors and is also more e-ciently computable.
Our construction improves on the construction of Saks, Srinivasan and Zhou [SSZ98] since
we construct an extractor rather than a disperser, and improves over the constructions of Ta-
Shma [TS96] since the additional randomness is logarithmic instead of slightly super-logarithmic.
The best previous construction of extractors using O(log n) additional randomness was the one
of Zuckerman [Zuc96b], that only works when the min-entropy is a constant fraction of the input
length, while in our construction every min-entropy of the form n
is admissible. (On the other
hand, the extractor of [Zuc96b] extracts a constant factor of the entropy, while we only extract
a constant root of it.) Our construction yields an entropy-rate optimal simulation of randomized
algorithms using weak random sources. In contrast to the result of [ACRT99] we can use a weak
random source to generate almost uniformly distributed random bits independently of the purpose
for which the random bits are to be used. 1
Our construction is not yet the best possible, since we lose part of the randomness of the source
and because the additional randomness is logarithmic only as long as
42 . (See also discussion
in Section 1.6 below.)
1.4 Techniques
This paper contains two main contributions.
The rst one is a connection (outlined in Section 2) between pseudorandom generators of a certain
kind and extractors. Our connection applies to certain pseudorandom generator constructions
that are based on the (conjectured) existence of predicates (decision problems) that can be uniformly
computed in time t(n) but cannot be solved by circuits of size much smaller than t(n). The
analysis of such constructions shows that if the predicate is hard, then it is also hard to distinguish
the output of the generator from the uniform distribution. This implication is proved by means of
a reduction showing how a circuit that is able to distinguish the output of the generator from the
uniform distribution can be transformed into a slightly larger circuit that computes the predicate.
(Impagliazzo and Wigderson [IW97] present one such construction with very strong parameters.)
Our result is that if the (truth table of the) predicate is chosen randomly, according to a distribution
with su-ciently high min-entropy, then the output of the generator is statistically close to uniform.
This statement is incomparable with standard analyses: we use a stronger assumption (that the
predicate is random instead of xed and hard) and prove a stronger conclusion (that the output
is statistically close to, instead of indistinguishable from, the uniform distribution). An immediate
application is that a pseudorandom generator construction of this kind is an extractor. Our result
1 Andreev et al. [ACRT99] show how to produce a sequence of bits that \look random" to a specic algorithm,
and their construction works by having oracle access to the algorithm. So it is not possible to generate random bits
\oine" before xing the application where the bits will be used.
has a straightforward proof, based on a simple counting argument. The main contribution, indeed,
is the statement of the result, rather than its proof, since it involves a new, more general, way of
looking at pseudorandom generator constructions. The Impagliazzo-Wigderson generator, using
our connection, is an extractor that beats some previous constructions and that is good enough
to imply entropy-rate optimal simulations of randomized algorithms. We stress that although the
Impagliazzo-Wigderson generator is known to be a pseudorandom generator only under unproved
conjectures, it is unconditionally a good extractor (i.e. we do not use any complexity-theoretic
assumption in our work).
Our second contribution is a construction that is simpler to describe and analyse (the generator
of Impagliazzo and Wigderson is quite complicated) and that has somewhat better parameters. Our
idea is to use a pseudorandom generator construction due to Nisan and Wigderson [NW94], that is
considerably simpler than the one of Impagliazzo and Wigderson (indeed the construction of Impagliazzo
and Wigderson contains the one of Nisan and Wigderson as one of its many components).
The Nisan-Wigderson generator has weaker properties than the Impagliazzo-Wigderson generator,
and our ideas outlined in Section 2 would not imply that it is an extractor as well. In Section 3
we show how to use error-correcting codes in order to turn the Nisan-Wigderson generator into a
very good extractor. Section 3 contains a completely self-contained treatment of the construction
and the analysis.
Perspective
For starters, our construction improves upon previous ones and solves the question of constructing
extractors that use a logarithmic amount of randomness, work for any min-entropy that is
polynomially related to the length of the input and have an output that is polynomially related
to the amount of entropy. Such a construction has been considered an important open question
(e.g. in [NTS98, Gol99]), even after Andreev et al. [ACRT99] showed that one does not need such
extractors in order to develop an entropy-rate optimal simulation of randomized algorithms via
random sources. Indeed, it was not clear whether the novel approach introduced by Andreev
et al. was necessary in order to have optimal simulations, or whether a more traditional approach
based on extractors was still possible. Our result claries this point, by showing that the traditional
approach su-ces.
Perhaps more importantly, our construction is simpler to describe and analyse then the most
recent previous constructions, and it uses a very dierent approach. Hopefully, our approach
oers more room for improvement than previous, deeply exploited, ones. Raz et al. [RRV99] have
already found improvements to our construction (see below). Tight results may come from some
combination of our ideas and previous ones.
Our use of results about pseudorandomness in the construction of extractors may come as a
surprise: pseudorandom generation deals with (and takes advantage of) a computational denition
of randomness, while extractors are combinatorial objects used in a framework where information-theoretic
randomness is being considered. In the past there have been some instances of (highly
non-trivial) results about computational randomness inspired by (typically trivial) information-theoretic
analogs, e.g. the celebrated Yao's XOR Lemma and various kind of \direct product"
results (see e.g. [GNW95]). On the other hand, it seemed \clear" that one could not go the other
way, and have information-theoretic applications of computational results. This prejudice might
be one reason why the connection discovered in this paper has been missed by the several people
who worked on weak random sources and on pseudorandomness in the past decade (including those
who did foundational work in both areas). Perhaps other important results might be proved along
similar lines.
1.6 Related Papers
The starting point of this paper was an attempt to show that every disperser can be modied
into an extractor having similar parameters. This was inspired by the fact (noted by several
people, including Andrea Clementi and Avi Wigderson) that every hitting set generator can be
transformed into a pseudorandom generator with related parameters, since the existence of hitting
set generators implies the existence of problems solvable in exponential time and having high
circuit complexity [ACR98] and the existence of such problems can be used to build pseudorandom
generators [BFNW93, IW97]. The fact that an information-theoretic analog of this result could
be true was suggested by the work done in [ACRT99], where proof-techniques from [ACR98] were
adapted in an information-theoretic setting. We were indeed able to use the Impagliazzo-Wigderson
generator in order to show that any construction of dispersers yields a construction of extractors
with slightly worse parameters. Oded Goldreich then pointed out that we were not making any
essential use of the disperser in our construction, and that we were eectively proving that the
Impagliazzo-Wigderson generator is an extractor (this result is described in Section 2). The use of
error-correcting codes and of the Nisan-Wigderson generator (as in Section inspired by an
alternative proof of some of the results of [IW97] due to Sudan et al. [STV99].
Shortly after the announcement of the results of this paper, Raz, Reingold and Vadhan [RRV99]
devised an improvement to our construction. In our construction, if the input has min-entropy k
and the output is required to be of length m, and " is a constant, then the additional randomness
is O(m 1= log(k=2m) (log n) log(k=2m)), which is very bad if, say, In [RRV99], the dependency
is O((log n) log(k=m)), so the randomness is bounded by O(log 2 n) even when
Furthermore, the running of the extractors of [RRV99] is poly(n; t) rather than poly(n; 2 t ) as in
the construction presented in this paper. Raz et al. [RRV99] also show how to recursively compose
their construction with itself (along the lines of [WZ93]) and obtain another construction where
and the additional randomness is O(log 3 n). Constructions of extractors with parameters
have applications to the explicit construction of expander graphs [WZ93]. In particular, Raz
et al. [RRV99] present constructions of expander graphs and of superconcentrators that improve
previous ones by Ta-Shma [TS96]. Raz et al. [RRV99] also improve the dependency that we have
between additional randomness and error parameter ".
Organization of the Paper
We present in Section 2 our connection between pseudorandom generator constructions and ex-
tractors. The main result of Section 2 is that the Impagliazzo-Wigderson generator [IW97] is a
good extractor. In Section 3 we describe and analyse a simpler construction based on the Nisan-
Wigderson generator [NW94] and on error correcting codes. Section 3 might be read independently
of Section 2.
2 The Connection Between Pseudorandom Generators and Extractor

This section describes our main idea of how to view a certain kind of pseudorandom generator as
an extractor. Our presentation is specialized on the Impagliazzo-Wigderson generator, but results
might be stated in a more general fashion.
2.1 Computational Indistinguishability and Pseudorandom Generators
We start by dening the notion of computational indistinguishability, and pseudorandom genera-
tors, due to Blum, Goldwasser, Micali and Yao [GM84, BM84, Yao82].
Recall that we denote by U n the uniform distribution over f0; 1g n . We say that two random
variables X and Y with the same range f0; 1g n are (S; ")-indistinguishable if for every
computable by a circuit of size S it holds
One may view the notion of "-closeness (that is, of statistical dierence less than ") as the
\limit" of the notion of (S; ")-indistinguishability for unbounded S.
Informally, a pseudorandom generator is an algorithm G : f0; 1g
")-indistinguishable from Um , for large S and small ". For derandomization of randomized
algorithms, one looks for generators, say,
is (m O(1) ; 1=3)-indistinguishable from Um . Such generators (if they were uniformly computable in
time poly(m)) would imply deterministic polynomial-time simulations of randomized polynomial-time
algorithms.
2.2 Constructions of Pseudorandom Generators Based on Hard Predicates
Given current techniques, all interesting constructions of pseudorandom generators have to rely on
complexity-theoretic conjectures. For example the Blum-Micali-Yao [BM84, Yao82] construction
(that has dierent parameters from the ones exemplied above) requires the existence of strong
one-way permutations. In a line of work initiated by Nisan and Wigderson [Nis91, NW94], there
have been results showing that the existence of hard-on-average decision problems in E is su-cient
to construct pseudorandom generators. (Recall that E is the class of decision problems solvable
deterministically in time 2 O(n) where n is the length of the input.) Babai et al. [BFNW93] present
a construction of pseudorandom generators that only requires the existence of decision problems in
having high worst-case complexity. An improved construction of pseudorandom generators from
worst-case hard problems is due to Impagliazzo and Wigderson [IW97], and it will be the main
focus of this section. The constructions of [NW94, BFNW93, IW97] require non-uniform hardness,
that is, use circuit size as a complexity measure. (Recent work demonstrated that non-trivial
constructions can be based on uniform worst-case conditions [IW98].)
The main result of [IW97] is that if there is a decision problem solvable in time 2 O(n) that cannot
be solved by circuits of size less than 2
n , for some
randomized
polynomial time algorithm has a deterministic polynomial-time simulation. A precise statement of
the result of Impagliazzo and Wigderson follows.
Theorem 2 ([IW97]) Suppose that there exists a family fP l g l0 of predicates
that is decidable in time 2 O(l) , and a constant
> 0 such that, for every su-ciently large l, P l has
circuit complexity at least 2
l .
Then for every constant " > 0 and parameter m there exists a pseudorandom generator
computable in time poly(m) such that IW (m) (U O(logm) ) is
(O(m); ")-indistinguishable from the uniform distribution, and
Results about pseudorandomness are typically proved by contradiction. Impagliazzo and Wigderson
prove Theorem 2 by establishing the following result.
Lemma 3 ([IW97]) For every pair of constants " > 0 and - > 0 there exists a positive constant
and an algorithm that on input a length parameter l and having oracle access
to a predicate computes a function IW
l such that for every
then P is computed by a circuit A that uses T -gates and whose size is at most 2 -l .
By a \circuit with T -gates" we mean a circuit that can use ordinary fan-in-2 AND and OR gates
and fan-in-1 NOT gates, as well as a special gate (of fan-in m) that computes T with unit cost.
This is the non-uniform analog of a computation that makes oracle access to T .
It might not be immediate to see how Theorem 2 follows from Lemma 3. The idea is that if
we have a predicate that cannot be computed by circuits of size 2 2-l , then
")-indistinguishable from uniform. This can be proved by contradiction: if T is
computed by a circuit of size 2 -l and is such that
then there exists a circuit A of size at most 2 -l that uses T -gates such that A computes P . If each
T -gate is replaced by the circuit that computes T , we end up with a circuit of size at most 2 2-l
that computes P , a contradiction to our initial assumption.
We stress that Lemma 3 has not been stated in this form by Impagliazzo and Wigderson [IW97].
In particular, the fact that their analysis applies to every predicate P and to every function T ,
regardless of their circuit-complexity, was not explicitely stated. On the other hand, this is not a
peculiar or surprising property of the Impagliazzo-Wigderson construction: in general in complexity
theory and in cryptography the correctness of a transformation of an object with certain assumed
properties (e.g. a predicate with large circuit complexity) into an object with other properties (e.g.
a generator whose output is indistinguishable from uniform) is proved by \black-box" reductions,
that work by making \oracle access" to the object and making no assumptions about it.
We also mention that three recent papers exploit the hidden generality of the pseudorandom
generator construction of Impagliazzo and Wigderson, and of the earlier one by Nisan and Wigderson
[NW94]. Arvind and Kobler [AK97] observe that the analysis of the Nisan-Wigderson generator
extends to \non-deterministic circuits," which implies the existence of pseudorandom generators for
non-deterministic computations, under certain assumptions. Klivans and Van Melkebeek [KvM99]
observe similar generalizations of the Impagliazzo-Wigderson generator for arbitrary non-uniform
complexity measures having certain closure properties (which does not include non-deterministic
circuit size, but includes the related measure \size of circuits having an NP-oracle"). The construction
of pseudorandom generators under uniform assumptions by Impagliazzo and Wigderson
[IW98] is also based on the observation that the results of [BFNW93] can be stated in a general
form where the hard predicate is given as an oracle, and the proof of security can also be seen as
the existence of an oracle machine with certain properties.
A novel aspect in our view (that is not explicit in [IW97, AK97, KvM99, IW98]) is to see the
Impagliazzo-Wigderson construction as an algorithm that takes two inputs: the truth-table of a
predicate and a seed. The Impagliazzo-Wigderson analysis says something meaningful even when
the predicate is not xed and hard (for an appropriate complexity measure), but rather supplied
dynamically to the generator. In the rest of this section, we will see that if the (truth table of the)
predicate is sampled from a weak random source of su-ciently large min-entropy, then the output
of the Impagliazzo-Wigderson generator is statistically close to uniform: that is, the Impagliazzo-
Wigderson generator is an extractor.
2.3 Using a Random Predicate Instead of a Hard One
Let us introduce the following additional piece of notation: let string x 2 f0; 1g n we
denote by hxi : f0; 1g l ! f0; 1g the predicate whose truth-table is x.
Lemma 4 Fix constants "; - > 0, and an integer parameter l. Consider the function Ext : f0; 1g n
dened as
dened in Equation (1) is a
Proof: We have to prove that for every random variable X of min entropy k  m-n - log n+log 1="
and for every
Let us x X and T and prove that Expression (2) holds for them. Let us call B  f0; 1g n the set
of bad strings x for which
For each such x, the analysis of Impagliazzo and Wigderson implies that there is a circuit of size
uses T -gates and that computes hxi. Since T is xed, and any two dierent predicates
are computed by two dierent circuits, we can conclude that the total number of elements of B
is at most the number of circuits of size with gates of fan-in at most m. So we have
Since X has high min-entropy, and B is small, the probability of picking an element of B when
sampling from X is small, that is
Then we have
2"
where the rst inequality is an application of the triangle inequality and the third inequality follows
from Expression (4) and the denition of B. 2
If we translate the parameters in a more traditional format we have the following extractor
construction.
Theorem 5 For every positive constants
and " there is a
and an explicit construction of
")-extractor
We proved that for every constant " > 0 and - > 0 there is a 0 <  < - such that there
is a (k; 2")-extractor construction where and the output length is
We can then set
=2 and
to get the parameters claimed in the theorem. 2
This is already a very good construction of extractors, and it implies an entropy-rate optimal
simulation of randomized algorithms using weak random sources.
We mentioned in Section 2.2 that Babai et al. [BFNW93] were the rst to give a construction
of pseudorandom generators based on worst-case hard predicates. In particular, a weaker version
of Lemma 3 is proved in [BFNW93], with similar parameters except that
O(l). The analysis of this section applies to the construction of Babai et al. [BFNW93], and
one can show that their construction gives extractors with the same parameters as in Theorem 5,
except that one would have
By deriving a more accurate estimation of the parameters in the Impagliazzo-Wigderson con-
struction, it would be possible to improve on the statement of Theorem 5. More specically, it
could be possible to have an explicit dependency of the parameter t from - and ", and an explicit
expression for (-;
). However, such improved analysis would not be better than the analysis of
the construction that we present in the next section, and so we do not pursue this direction.
3 Main Result
In this section we present a construction of extractors based on the Nisan-Wigderson generator and
error-correcting codes. The Nisan-Wigderson generator is simpler than the Impagliazzo Wigderson
generator considered in the previous section, and this simplicity will allow us to gain in e-ciency.
The advantages of the construction of this section over the construction of the previous section
are better quantitative parameters and the possibility of giving a self-contained and relatively simple
presentation. The subsequent work of Raz et al [RRV99] took the construction of this section as a
starting point, and improved the primitives that we use.
3.1

Overview

The Nisan-Wigderson generator works similarly to the Impagliazzo-Wigderson one: it has access
to a predicate, and its output is indistinguishable from uniform provided that the predicate is hard
(but, as will be explained in a moment, a stronger notion of hardness is being used). This is proved
by means of a reduction that shows that if T is a test that distinguishes the output of the generator
with predicate P from uniform, then there is a small circuit with one T -gate that approximately
computes P . That is, the circuit computes a predicate that agrees with P on a fraction of inputs
noticeably bounded away from 1/2.
Due to this analysis, we can say that the output of the Nisan-Wigderson generator is indistinguishable
from uniform provided that the predicate being used is hard to compute approximately, as
opposed to merely hard to compute exactly, as in the case of the Impagliazzo-Wigderson generator.
We may be tempted to dene and analyse an extractor Ext based on the Nisan-Wigderson
generator using exactly the same approach of the previous section. Then, as before, we would
assume for the sake of contradiction that a test T distinguishes the output Ext(X; U t ) of the
extractor from the uniform distribution, and we would look at how many strings x are there such
that j Pr[T (Ext(x; U t can be large. For each such x we can say that there
is a circuit of size S that describes a string whose Hamming distance from x is noticeably less than
1/2. Since there are about 2 S such circuits, the total number of bad strings x is at most 2 S times
the number of strings that can belong to a Hamming sphere of radius about 1/2. If X is sampled
from a distribution whose min-entropy is much bigger then the logarithm of the number of possible
bad x, then we reach a contradiction to the assumption that T was distinguishing Ext(X; U t )
from uniform. When this calculation is done with the actual parameters of the Nisan-Wigderson
generator, the result is very bad, because the number of strings that belong to a Hamming sphere
of the proper radius is huge. This is, however, the only point where the approach of the previous
section breaks down.
Our solution is to use error-correcting codes, specically, codes with the property that every
Hamming sphere of a certain radius contains a small number of codewords. We then dene an
extractor Ext that on input x and s rst encodes x using the error-correcting code, and then
applies the Nisan-Wigderson generator using s as a seed and the encoding of x as the truth table
of the predicate. Thanks to the property of the error-correcting code, the counting argument of
the previous section works well again.
3.2 Preliminaries
In this section we state some known technical results that will be used in the analysis of our
extractor. For an integer n we denote by [n] the set ng. We denote by u 1 u 2 the string
obtained by concatenating the strings u 1 and u 2 .
3.2.1 Error-correcting codes
Error-correcting codes are one of the basic primitives in our construction. We need the existence
of codes such that few codewords belong to any given Hamming ball of su-ciently small radius.
Lemma 6 (Error Correcting Codes) For every n and - there is a polynomial-time computable
encoding
1=-) such that every ball of Hamming radius
(1=2 -)n in f0; 1g  n contains at most 1=- 2 codewords. Furthermore
n can be assumed to be a power
of 2.
Stronger parameters are achievable. In particular the length of the encoding can be
However, the stronger bounds would not improve our constructions. Standard codes are good
enough to prove Lemma 6. We sketch a proof of the lemma in the Appendix.
3.2.2 Designs and the Nisan-Wigderson Generator
In this section we cite some results from [NW94] in a form that is convenient for our application.
Since the statements of the results in this section are slightly dierent from the corresponding
statements in [NW94], we also present full proofs.
Denition 7 (Design) For positive integers m, l, a  l, and t  l, a (m; t; l; a) design is a family
of sets such that
for every i
Lemma 8 (Construction of Design [NW94]) For every positive integers m, l, and a  l there
exists a (m; t; l; a) design where
a +1  l 2
a . Such a design can be computed deterministically in
O(2 t m) time.
The deterministic construction in Lemma 8 was presented in [NW94] for the special case of
log m. The case for general a can be proved by using the same proof, but a little care is
required while doing a certain probabilistic argument. The proof of Lemma 8 is given in Appendix
A.2.
The following notation will be useful in the next denition: if S  [t], with
(where then we denote by y jS 2 f0; 1g l the string y s 1
y s l .
Denition 9 (NW Generator [NW94]) For a function f : f0; 1g l ! f0; 1g and an (m; t; l; a)-
as
Intuitively, if f is a hard-on-average function, then f() evaluated on a random point x is an \un-
predictable bit" that, to a bounded adversary, \looks like" a random bit. The basic idea in the
Nisan-Wigderson generator is to evaluate f() at several points, thus generating several unpredictable
output bits. In order to have a short seed, evaluation points are not chosen independently,
but rather in such a way that any two points have \low correlation." This is where the denition of
design is useful: the random seed y for the generator associates a truly random bit to any element
of the universe [t] of the design. Then the i-th evaluation point is chosen as the subset of the
bits of y corresponding to set S i in the design. Then the \correlation" between the i-th and the
j-th evaluation point is given by the  a bits that are in S i \ S j . It remains to be seen that the
evaluation of f at several points having low correlation looks like a sequence of random bits to a
bounded adversary. This is proved in [NW94, Lemma 2.4], and we will state the result in a slightly
dierent form in Lemma 10 below.
For two functions f; and a number 0    1 we say that approximates f
within a factor  if f and g agree on at least a fraction  of their domain, i.e. Pr x
(Analysis of the NW Generator [NW94]) Let S be an (m; l; a)-design, and T :
1g. Then there exists a family G T (depending on T and S) of at most 2 m2 a +log m+2
functions such that for every function f : f0; 1g l ! f0; 1g satisfying
there exists a function , such that g() approximates f() within 1=2
"=m.
Proof: [Of Lemma 10] We follow the proof of Lemma 2.4 in [NW94]. The main idea is that if T
distinguishes NW f;S () from the uniform distribution, then we can nd a bit of the output where
this distinction is noticeable.
In order to nd the \right bit", we will use the so-called hybrid argument of Goldwasser and
Micali [GM84]. We dene m+1 distributions D dened as follows: sample a string
for a random y, and then sample a string r 2 f0; 1g m according to the uniform
distribution, then concatenate the rst i bits of v with the last m i bits of r. By denition, Dm
is distributed as NW f;S (y) and D 0 is the uniform distribution over f0; 1g m .
Using the hypothesis of the Lemma, we know that there is a bit b 0 2 f0; 1g such that
Pr y
We then observe that
In particular, there exists an index i such that
Now, recall that
and
)f(y jS i
We can assume without loss of generality (up to a renaming of the indices) that S lg.
Then we can see y 2 f0; 1g t as a pair (x; z) where
l . For
every us dene h j (x; note that h j (x; z) depends on jS i \ S j j  a
bits of x and on l jS i \ S j j  l a bits of z.
Using this notation (and observing that for a 0/1 random variable the probability that the
random variable is 1 is equal to the expectation of the random variable) we can rewrite Expression
(5) as
We can use an averaging argument to claim that we can x r to some values
c i+1    c m , as well as x z to some value w, and still have
Let us now consider a new function F : f0; 1g l+1 ! f0; 1g m dened as F (x;
. Using F , renaming r i as b, and moving
back to probability notation, we can rewrite Expression (6) as
Pr
That is, using T 0 and F it is possible to distinguish a pair of the form (x; f(x)) from a uniform
string of length l +1. We will now see that, given F () and T 0 (), it is possible to describe a function
g() that agrees with f() on a fraction 1=2 + "=m of the domain.
Consider the following pick a random b 2 f0; 1g, and compute T 0
us call g b (x) the function performing
the above computation, and let us estimate the agreement between f() and g b (), averaged over
the choice of b.
Pr
b;x
b;x
b;x
b;x
b;x
b;x
b;x
Pr b;x
Over the choices of x and b, the probability that we guess f(x) is  1=2 +"=m, hence there is a
1g such that g b 1
approximates f to within 1=2 Once T and F are given, we can
specify
using two bits of information (the bit b 1 , plus the bit b 0 such that T 0
We now observe that F can be totally described by using no more than log m+(i 1)2 a +(m i) <
log a bits of information. Indeed, we use log m bits to specify i, then for every j < i and
for every x we have to specify f(h j (x; w)). Since h j (x; w) only depends on the bits of x indexed by
just have to specify 2 a values of f for each such j. For j > i we have to specify c j .
Overall, we have a function g() that approximates f to within 1=2 "=m and that, given T ,
can be described using 2 log m+m2 a bits. We dene G T as containing all functions g() that can
be dened in this way, over all possible description. 2
3.3 Construction
The construction has parameters n, . It can be veried
that the constraints on the parameters imply that (because we have
be as in Lemma 6, with so that
For an element u 2 f0; 1g n , dene
be as in
Lemma 8, such that
log(k=2m), and
e
log(k=2m)  l 2
log(k=2m)
By our choice of parameters, and by choosing c appropriately, we have that m > t.
Then we
u(y jS 1
3.4 Analysis
Lemma 11 Let Ext be as in Equation (7). For every xed predicate
are at most 2 2+m2 a
strings u 2 f0; 1g n such that
Proof: It follows from the denition of Ext and from Lemma 10 that if u is such that (8) holds,
then there exists a function g : f0; 1g l ! f0; 1g m in G T and a bit b 2 f0; 1g such that the function
There are at most 2 2+t l+log m+m2 a functions g 2 G T , and we have l > log n > log m. Further-
more, each such function can be within relative distance 1=2 "=m from at most (m=") 2 functions
u() coming from the error correcting code of Lemma 6.
We conclude that 2 2+2 log(m=")+t+m2 a
is an upper bound on the number of strings u for which
Expression (8) can occur. 2
Theorem 12 Ext as dened in Equation (7) is a (k; 2")-extractor.
Proof: We rst note that, by our choice of parameters, we have m2 a = k=2. Also, k=2 > 4m and
1g. From Lemma 11 we have that the probability that
sampling a u from a source X of min-entropy k we have
is at most 2 2+t+m2 a +log(m 2 =" 2 which is at most " by our choice of parameters. A Markov
argument shows that
now follows from Theorem 12 and by the choice of parameters in the previous section.

Acknowledgments

Oded Goldreich contributed an important idea in a critical phase of this research; he also contributed
very valuable suggestions on how to present the results of this paper. I thank Oded Goldreich, Sha
Goldwasser, Madhu Sudan, Salil Vadhan, Amnon Ta-Shma, and Avi Wigderson for several helpful
conversations. This paper would have not been possible without the help of Adam Klivans, Danny
Lewin, Salil Vadhan, Yevgeny Dodis, Venkatesan Guruswami, and Amit Sahai in assimilating the
ideas of [NW94, BFNW93, Imp95, IW97]. Thanks also to Madhu Sudan for hosting our reading
group in the Spring'98 Complexity Seminars at MIT. This work was mostly done while the author
was at MIT, partially supported by a grant of the Italian CNR. Part of this work was also done
while the author was at DIMACS, supported by a DIMACS post-doctoral fellowship.



--R

A new general derandomization method.
Weak random sources

BPP has subexponential time simulations unless EXPTIME has publishable proofs.
Free bits
How to generate cryptographically strong sequences of pseudo-random bits

Unbiased bits from sources of weak randomness and probabilistic communication complexity.
Dispersers, deterministic ampli
Probabilistic encryption.
On Yao's XOR lemma.
Modern Cryptography
Tiny families of functions with random properties: A quality-size trade-o for hashing
Another proof that BPP


Randomness versus time: De-randomization under a uniform assumption
Graph non-isomorphism has subexponential size proofs unless the polynomial hierarchy collapses
Introduction to Parallel Algorithms and Architectures.
The Theory of Error-Correcting Codes
Pseudorandom bits for constant depth circuits.
Extracting randomness: How and why.
Extrating randomness
Hardness vs randomness.
More deterministic simulation in Logspace.
Extracting all the randomness and reducing the error in Trevisan's extractors.
Tight bounds for depth-two superconcentrators
Explicit OR-dispersers with polylogarithmic degree
Pseudorandom generators without the XOR lemma.
Generating quasi-random sequences from slightly random sources
Computing with very weak random sources.
Construction of extractors using pseudo-random generators
On extracting randomness from weak random sources.
Almost optimal dispersers.
Various techniques used in connection with random digits.
Random polynomial time is equal to slightly random polynomial time.
Expanders that beat the eigenvalue bound: Explicit construction and applications.
Theory and applications of trapdoor functions.
General weak random sources.
On unapproximable versions of NP-complete problems

--TR
How to generate cryptographically strong sequences of pseudo-random bits
Generating quasi-random sequences from semi-random sources
Unbiased bits from sources of weak randomness and probabilistic communication complexity
Introduction to parallel algorithms and architectures
More deterministic simulation in logspace
Expanders that beat the eigenvalue bound
Hardness vs. randomness
BPP has subexponential time simulations unless EXPTIME has publishable proofs
On extracting randomness from weak random sources (extended abstract)
Randomness-optimal sampling, extractors, and constructive leader election
On Unapproximable Versions of <i>NP</i>-Complete Problems
exponential circuits
Explicit OR-dispersers with polylogarithmic degree
A new general derandomization method
Almost optimal dispersers
Tiny families of functions with random properties
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Extracting all the randomness and reducing the error in Trevisan''s extractors
Pseudorandom generators without the XOR Lemma (extended abstract)
Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
Extracting randomness
Weak Random Sources, Hitting Sets, and BPP Simulations
On Resource-Bounded Measure and Pseudorandomness
Extracting Randomness
Hard-core distributions for somewhat hard problems
Tight bounds for depth-two superconcentrators
Randomness vs. Time

--CTR
Amnon Ta-Shma , David Zuckerman , Shmuel Safra, Extractors from Reed-Muller codes, Journal of Computer and System Sciences, v.72 n.5, p.786-812, August 2006
Venkatesan Guruswami, Better extractors for better codes?, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Harry Buhrman , Troy Lee , Dieter Van Melkebeek, Language compression and pseudorandom generators, Computational Complexity, v.14 n.3, p.228-255, January 2005
Russell Impagliazzo, Can every randomized algorithm be derandomized?, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Anup Rao, Extractors for a constant number of polynomially small min-entropy independent sources, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Troy Lee , Andrei Romashchenko, Resource bounded symmetry of information revisited, Theoretical Computer Science, v.345 n.2-3, p.386-405, 22 November 2005
Tzvika Hartman , Ran Raz, On the distribution of the number of roots of polynomials and explicit weak designs, Random Structures & Algorithms, v.23 n.3, p.235-263, October
Christopher Umans, Pseudo-random generators for all hardnesses, Journal of Computer and System Sciences, v.67 n.2, p.419-440, September
Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Paolo Ferragina , Raffaele Giancarlo , Giovanni Manzini , Marinella Sciortino, Boosting textual compression in optimal linear time, Journal of the ACM (JACM), v.52 n.4, p.688-713, July 2005
Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Peter Bro Miltersen , N. V. Vinodchandran, Derandomizing Arthur-Merlin games using hitting sets, Computational Complexity, v.14 n.3, p.256-279, January 2005
Ronen Shaltiel , Christopher Umans, Simple extractors for all min-entropies and a new pseudorandom generator, Journal of the ACM (JACM), v.52 n.2, p.172-216, March 2005
Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity Via Uniform Reductions, Computational Complexity, v.16 n.4, p.331-364, December  2007
Jin-Yi Cai , Hong Zhu, Progress in computational complexity theory, Journal of Computer Science and Technology, v.20 n.6, p.735-750, November 2005
error-correcting codes;extractors;pseudorandomness