How strong is Nisanʼs pseudo-random generator?

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.