<p>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.  </p>

CC BY-SA 2.5
2010-10-17T00:24:24.137Z
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
CC BY-SA 2.5
2010-10-17T04:17:13.407Z
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
CC BY-SA 2.5
2010-10-16T17:43:25.607Z
2010-10-16T17:43:25.607Z
Noam
<p>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) ?</p>

CC BY-SA 2.5
2010-10-16T16:18:11.203Z
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
<cc.complexity-theory><space-bounded><derandomization>
Does Nisan's pseudo-random generator relativize?
Sebastian Ben Daniel
# Does Nisan's pseudo-random generator relativize?

(Asked by: username_0 on 2010-10-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) ?

**Tags:** cc.complexity-theory, space-bounded, derandomization

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2010-10-16. Score: 18 | Accepted answer

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:**
> **username_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.  
> **username_2**: 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.  

---

