Computer Science/Discrete Mathematics Seminar II

Let f(x_1,...,x_n) be a low degree polynomial over F_p. I will prove that there always exists a small set S of variables, such that `most` Fourier coefficients of f contain some variable from the set S. As an application, we will get a derandomized sampling of elements in F_p^n which `look uniform` to f. The talk will be self contained, even though in spirit it is a continuation of my previous talk on pseudorandom generators for CC0[p]. Based on joint work with Amir Shpilka and Partha Mukhopadhyay.