Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

by Salil Vadhan and Colin Jia Zheng

Oded's comments

After two decades of research, the barrier envisioned by Johan Hastad (in a private discussion with me) has been reached, and now the goal is to break it. The barrier that I refer to is a seed length of $O(n^3)$ for a PRG (pseudorandom generator) constructed based on a OWF (one-way function) that operates on $n$-bit long strings. The barrier arises from the paradigm of ``smoothing'' the random variables that arise from applying the OWF to a uniformly distributed $n$-bit long string, where smoothing means manipulating them into a random variable with min-entropy sufficiently close to its entropy (so that randomness extraction can be safely applied).

The construction presented in this work is relatively simple, and has a clear intuitive appeal. One may still say that Johan's barrier has not been reached, because the OWF is applied to $tildeO(n^3)$ strings rather than to $tildeO(n^2)$ strings (but this seems a bit too picky). In any case, we now stand in front of the more demanding goal set by Leonid Levin: Presenting a construction of a PRG with seed length $O(n)$ based on any OWF that operates on $n$-bit strings. Two decades ago Johan thought that this is out of our reach; is it still so?

The original abstract

See ECCC TR11-141.

Back to list of Oded's choices.