Abstract
The development of unconditional pseudorandom generators that fool small-space computations has seen much research activity and significant progress.
Notably, Nisan's generator stretches a seed of O(log^2 n) bits to n bits that cannot be distinguished from uniform by an O(log n)-space algorithm. However, reducing the seed length to O(log n) bits -- and, thus, proving RL=L -- remains an elusive goal. Subsequent improvements to Nisan's result only address special cases, and it seems new techniques are needed.
For other classes, such as small-depth circuits, halfspaces, and polynomials, there has been success in using Fourier-analytic techniques to construct pseudorandom generators.
This talk will discuss the use of Fourier-analytic techniques to construct pseudorandom generators that fool constant-space computations. In particular, for constant-width branching programs (a nonuniform model of constant-space computation), we can construct pseudorandom generators with polylogarithmic seed length for two special cases: permutation branching programs, and width 3. The generator uses small bias spaces combined with the ``mild pseudorandom restrictions'' approach of Gopalan, Meka, Reingold, Trevisan, and Vadhan. One advantage of the Fourier-analytic approach is that the pseudorandomness property is invariant under permutations of the output bits of the pseudorandom generator, which is a property that Nisan's generator lacks.