Talks
Spring 2017

# PRGs for Small Space via Fourier Analysis

Thursday, March 9th, 2017 11:40 am12:10 pm

### Add to Calendar

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.