On Sums of INW Pseudorandom Generators

We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let $X$ be the $n$-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter $\lambda$. We prove that the bitwise XOR of $t$ independent copies of $X$ fools width-$w$ programs with error $n^{\log(w + 1)} \cdot (\lambda \cdot \log n)^t$. Notably, this error bound is meaningful even for relatively large values of $\lambda$ such as $\lambda = 1/O(\log n)$.

Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs — it just gives a new way of re-proving the well-known $O(\log^2 n)$ bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our "XOR of INW" approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-$3$ programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably $\Omega(\log^2 n)$.

Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on $t$ correlated seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.

A "pseudorandom generator" is an algorithm that flips a coin a few times and outputs a long sequence of bits that "appear random" in some sense. In this paper, we present a pseudorandom generators whose output bits appear random from the perspective of any observer who has a tiny amount of memory and who only looks at each bit one time in a predetermined order. Quantitatively speaking, our pseudorandom generator isn't any better than prior work, but we argue that our new generator might be a step on a path to near-optimal generators.