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