Spring 2017

Pseudorandomness Seminar

Tuesday, February 28th, 2017, 4:30 pm5:30 pm

Add to Calendar

Parent Program: 

Calvin Lab Room 116

Fooling Fourier Shapes

We present recent work providing a nearly optimal, explicit pseudorandom generator against linear threshold functions. The basic idea is to fool the Fourier transform of the corresponding linear forms rather than the threshold function. This generalizes further to fooling a class of functions that we call "Fourier shapes". We discuss the generator and some of its applications.