## Better pseudorandom generators from milder pseudorandom restrictions

by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

#### Oded's comments

This is another recent work (cf. Choise Nr 103)
that uses pseudorandom restrictions to obtain improved pseudorandomn
generators; this time for combinatorial rectangles and read-once CNFs.

#### The original abstract

We present an iterative approach to constructing pseudorandom
generators, based on the repeated application of mild
pseudorandom restrictions. We use this template to construct
pseudorandom generators for combinatorial rectangles and
read-once CNFs and a hitting set generator for width-3 branching
programs, all of which achieve near optimal seed-length even in
the low-error regime: We get seed-length $\tilde{O}(\log
(n/\epsilon))$ for error $\epsilon$. Previously, only
constructions with seed-length $O(\log^{3/2} n)$ or $O(\log^2 n)$
were known for these classes with polynomially small error.

The (pseudo)random restrictions we use are milder than those
typically used for proving circuit lower bounds in that we only
set a constant fraction of the bits at a time. While such
restrictions do not simplify the functions drastically, we show
that they can be derandomized using small-bias spaces.

See
ECCC TR12-123.

Back to
list of Oded's choices.