cc.complexity-theory space-bounded derandomization: Updated Wed, 22 Jun 2022 11:26:37 GMT

Does Nisan's pseudo-random generator relativize?

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) ?

Solution

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.

Comments (2)

+0 – 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. — Oct 17, 2010 at 00:24
+5 – 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. — Oct 17, 2010 at 04:17

References

https://cstheory.stackexchange.com/questions/2236