Talks
Spring 2017

PRGs for Small Space via Fourier Analysis

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

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.