| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428624 | Information Processing Letters | 2011 | 5 Pages |
We study the resilience of the classical pseudo-random generator (PRG) of Nisan (1992) [6] against space-bounded machines that make multiple passes over the input. Nisanʼs PRG is known to fool log-space machines that read the input once. We ask what are the limits of this PRG regarding log-space machines that make multiple passes over the input. We show that for every constant k Nisanʼs PRG fools log-space machines that make logkn passes over the input, using a seed of length logk′n, for some k′>kk′>k. We complement this result by showing that in general Nisanʼs PRG cannot fool log-space machines that make nO(1)nO(1) passes even for a seed of length 2Θ(logn). The observations made in this note outline a more general approach in understanding the difficulty of derandomizing BPNC1BPNC1.
► Nisanʼs PRG was originally shown to fool one way log-space machines. ► We show that Nisanʼs PRG also fools multiple-pass log-space machines. ► For polynomially many passes we can break Nisanʼs PRG in log-space.
