From Extractors to Pseudorandom Generators?

Question

Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions:

http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf

Is there a meaningful converse? I.e., can "natural" constructions of extractors be thought of as pseudorandom generators (PRG) constructions?

Extractor constructions seem to correspond to distributions over PRGs (such that any distinguisher won't succeed in distinguishing for almost all of them). Are there known applications for this?

Answer 1

Salil Vadhan wrote to me that the answer to my question is known, and PRGs are equivalent to extractors.

Quoting him:

"See Proposition 21 and the discussion following it in my survey http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (There's a typo - "black-box hardness amplifier" should be "black-box PRG construction")

It says extractors are equivalent to black-box PRG constructions where you only care about the amount of advice, and not the running time, in the reduction. Asking for bounded running time amounts to asking for extractors with "local list-decoding"."

Answer 2

This is a beautiful research question with several facets to it, and there are different ways of formalizing the question depending on whether by extractor you mean seeded extractor or seedless extractor and whether by PRG you mean PRG for Boolean circuits or a more specialized family (e.g., epsilon-biased spaces). Here's a few informal thoughts off the top of my head (but not a full answer):

• For seeded extractors vs black-box PRGs (as in Nisan-Wigderson), it seems that black-box PRG is a stronger object than extractor. If you look at Trevisan's extractor, it's not only a polynomial-time computable extractor but has an important extra property. Namely, the analysis has a local and efficient computational element in it (namely, a local list-decoding algorithm). This extra feature is not so important for an extractor (as a combinatorial object, even if we require the extractor to be polynomial-time computable) but is crucial for a PRG (so that a distinguisher can be efficiently transformed into an algorithm for computing the hard function). In fact this can be formalized, and Ta-Shma and Zuckerman have already formalized the definition of a "black-box PRG" in their paper "Extractor Codes". They show that black-box PRGs can be used to construct extractors. For the converse, I think one can show that any extractor that satisfies the above property corresponds to a black-box PRG (in the extractor language, this would mean that the resulting extractor code must have an efficient soft-decision list-decoder). You may also find Vadhan's paper "The Unified Theory of Pseudorandomness" relevant to this discussion.

• In the world of seedless extractors, Trevisan and Vadhan show that hard functions for a specific family of circuits result in extractors for that family (paper "Extractors for Samplable Sources"). So, for example a function that is really hard on average for AC0 can extract from sources sampled by AC0 circuits (if the min-entropy of the source is sufficiently large). Hard functions naturally relate to PRGs (as observed by Nisan-Wigderson). So here we again get a somewhat different interplay between PRGs and seedless extractors. It is however less clear how one can use an extractor for samplable sources (maybe satisfying some additional properties) to get a PRG (the next bullet point gives a partial answer to this). This direction may be less interesting than the above discussion for seeded extractors since to this date we don't have really good constructions of extractors for samplable sources.

• From a combinatorial point of view, there is a similarity between PRGs and extractors. We can look at a PRG as a set $S$ of points in $\{0,1\}^n$ (the outcomes of the PRG for all possible seeds) or equivalently, a coloring of the $n$-dimensional hypercube in two colors. Similarly, an extractor with one bit of output (or any Boolean function, for that matter) can be seen as a set of points (those for which the extractor evaluates $0$) or coloring (in general, the number of colors would be $2^m$ where $m$ is the output length). Now, a PRG with point set $S$ fools a function with point set $F$ iff $|S \cap F|/|S|$ is close to $|F|/2^n$. Also, an extractor with point set $F$ extracts from a flat source that is uniformly distributed on a set of points $S$ iff $|S \cap F|/|S|$ is close to $1/2$. This similarity between the definitions allows one to deduce some meaningful conclusions. For example, look at an affine extractor over $\{0,1\}^n$ that extracts from min-entropy $n-1$, and outputs $1$ bit. Now consider the set $S$ of the strings that are mapped to, say, $0$ by the extractor and translate it as above to a "PRG" (with seed length $n-1$). Now the coloring interpretation above shows that the resulting function is indeed a PRG for linear functions; that is, we get an epsilon-biased generator from an extractor. This is a meaningful relationship but probably not so useful since the resulting PRG stretches the seed only by one bit. Maybe a better result can be deduced if the extractor outputs more bits, but I haven't checked that carefully.

Answer 3

There is a nice paper of Chris Umans on the analogue of this question for dispersers: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf

He shows that dispersers that have a polynomial-time reconstruction procedure, but not necessarily the local decoding property, imply the existence of hitting set generators.

Here is another way to view it: Extractors may be viewed as list-recoverable codes (which is a stronger variant of list-decodable codes), and black-box PRGs may be viewed of local list-recoverable codes. Dispersers may be viewed as list-recoverable codes for zero-error. What Chris shows is that a list-recoverable code for zero-error that has a polynomial-time list-recovery procedure implies the existence of a list-recoverable code with local list-recovery procedure.