Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs
{{output}}
The classic Impagliazzo-Nisan-Wigderson (INW) pseudorandom generator (PRG) (STOC '94) for space-bounded computation uses a seed of length O ( log n · log ( n w / ε ) + log d ) to fool ordered branching programs of length n, width w, and alphabet siz... ...
