|COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II|
|Topic:||Fourier Spectrum of Polynomials Over Finite Fields|
|Affiliation:||Member, School of Mathematics|
|Date:||Tuesday, November 2|
|Time/Room:||10:30am - 11:30am/S-101|
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.