ECCC-Report TR11-047https://eccc.weizmann.ac.il/report/2011/047Comments and Revisions published for TR11-047en-usFri, 08 Apr 2011 14:36:10 +0300
Paper TR11-047
| Two Comments on Targeted Canonical Derandomizers |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2011/047We 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. Fri, 08 Apr 2011 14:36:10 +0300https://eccc.weizmann.ac.il/report/2011/047