## Two Comments on Targeted Canonical Derandomizers

#### Webpage for a paper by Oded Goldreich

#### Abstract

We revisit the notion of a {\em targeted canonical derandomizer},
introduced in our recent ECCC Report (TR10-135)
as a uniform notion of a pseudorandom generator
that suffices for yielding BPP=P.
The original notion was derived (as a variant of the standard notion
of a canonical derandomizer) by providing both the distinguisher
and the generator with the same auxiliary-input.
Here we take one step further and consider pseudorandom generators
that fool a single circuit that is given to them as auxiliary input.
Building on TR10-135, we show that such pseudorandom generators
exist if and only if BPP=P, which means that they exist
if and only if targeted canonical derandomizers
(of exponential stretch, as in TR10-135) exist.
We also relate such targeted canonical derandomizer to targeted hitters,
which are the analogous canonical derandomizers for RP.

#### Material available on-line

- First version posted:
Apr'11.
- Revisions: none yet.

Back to
either Oded Goldreich's homepage
or general list of papers.