Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


In this paper we give the first construction of a pseudorandom generator, with seed length $O(log n)$, for $mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(log n)$ for any constant error $epsilon>0$. In fact, we obtain our generator by fooling distributions generated by low degree polynomials, over $mathbb{F}_p$, {em when evaluated on the Boolean cube}. This result significantly extends previous constructions that either required a long seed~cite{LubyVeWi93} or that could only fool the distribution generated by linear functions over $mathbb{F}_p$, when evaluated on the Boolean cube~cite{LovettReTrVa09,MekaZu09:small_bias}.

Enroute of constructing our PRG, we prove two structural results for low degree polynomials over finite fields that can be of independent interest.

egin{enumerate} item Let $f$ be an $n$-variate degree $d$ polynomial over $mathbb{F}_p$. Then, for every $epsilon>0$ there exists a subset $S subset [n]$, whose size depends only on $d$ and $epsilon$, such that $sum_{alpha in mathbb{F}_p^n: alpha e 0, alpha_S=0}|hat{f}(alpha)|^2 leq epsilon$. Namely, there is a constant size subset $S$ such that the total weight of the nonzero Fourier coefficients that do not involve any variable from $S$ is small.

item Let $f$ be an $n$-variate degree $d$ polynomial over $mathbb{F}_p$. If the distribution of $f$ when applied to uniform zero-one bits is $epsilon$-far (in statistical distance) from its distribution when applied to biased bits, then for every $delta>0$, $f$ can be approximated over zero-one bits, up to error $delta$, by a function of a small number (depending only on $epsilon,delta$ and $d$) of lower degree polynomials. end{enumerate}

Questions and Answers

You need to be logged in to be able to post here.