Videos

Fourier Spectrum of Polynomials Over Finite Fields

Presenter
November 2, 2010
Keywords:
  • Computer Science and Discrete Mathematics (CSDM)
Abstract
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.