Fourier Spectrum of Polynomials Over Finite Fields

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II
Topic:Fourier Spectrum of Polynomials Over Finite Fields
Speaker:Shachar Lovett
Affiliation:Member, School of Mathematics
Date:Tuesday, November 2
Time/Room:10:30am - 11:30am/S-101
Video Link:https://video.ias.edu/csdm/lovett2

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.