Nisan proved in "Psuedorandom Generators for Space-Bounded Computation", that there exists a pseudo-random generator which "fools" space-bounded computations. Does this construction hold for every oracle (at least for non-adaptive queries) ?
16
$\begingroup$
$\endgroup$
asked Oct 16 '10 at 15:24
-
$\begingroup$ I can't answer this question, yet I wanted to point to a related paper titled "Hardness vs. Randomness" (dx.doi.org/10.1016/S0022-0000(05)80043-1), which you may find useful. $\endgroup$ – M.S. Dousti Oct 16 '10 at 16:18
18
$\begingroup$
$\endgroup$
It depends on whether in your definition of the Oracle TM, the oracle query tape is also bounded to be of logarithmic size: if it is bounded then the PRG fools also L^A for any A too, if it is not bounded then A can contain the list of "pseudorandom strings" and thus L^A will not be fooled.
-
$\begingroup$ This is true for all pseudo-random generators, however, for example, NW generator does relativizies if we assume hardness against the oracle we want to fool. I was wondering whether we can do something of this kind also for this generator. $\endgroup$ – Sebastian Ben Daniel Oct 17 '10 at 0:24
-
5$\begingroup$ Since this PRG is completely specified (ie not based on some other "hard function f"), it's not clear how to use the oracle in the relativized setting. $\endgroup$ – Noam Oct 17 '10 at 4:17
