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


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