Recently Added

Panel Discussion: Secularism and Human Rights: Basic Human Rights in History, Philosophy, Political Science, and Sociology

Moderator: Harold Shapiro, President Emeritus and Professor of Economics and Public Affairs, Princeton University
Trustee, Institute for Advanced Study
November 13, 2010

Panelists:
Didier Fassin, James D. Wolfensohn Professor, School of Social Science
Jonathan Israel, Professor, School of Historical Studies
Avishai Margalit, George F. Kennan Professor, School of Historical Studies
Joan Wallach Scott, Harold F. Linder Professor, School of Social Science

Fourier Spectrum of Polynomials Over Finite Fields

Shachar Lovett
Institute for Advanced Study
November 2, 2010

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.