16

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

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116
Sebastian Ben Daniel
  • 827
  • 5
  • 9
  • I can't answer this question, yet I wanted to point to a related paper titled "Hardness vs. Randomness" (http://dx.doi.org/10.1016/S0022-0000(05)80043-1), which you may find useful. – Sadeq Dousti Oct 16 '10 at 16:18

1 Answers1

18

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.

Noam
  • 9,369
  • 47
  • 58
  • 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. – Sebastian Ben Daniel Oct 17 '10 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. – Noam Oct 17 '10 at 04:17