Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-047 | 8th April 2011 14:35

Two Comments on Targeted Canonical Derandomizers


Authors: Oded Goldreich
Publication: 8th April 2011 14:36
Downloads: 1201


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.

ISSN 1433-8092 | Imprint