Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields

In this paper we give the first construction of a pseudorandom generator, with seed length O(log n), for CC⁰[p], the class of constant-depth circuits with unbounded fan-in MOD_p gates, for some prime p. More accurately, the seed length of our generator is O(log n) for any constant error ϵ > 0. In fact, we obtain our generator by fooling distributions generated by low degree polynomials, over F_p, when evaluated on the Boolean cube. This result significantly extends previous constructions that either required a long seed or that could only fool the distribution generated by linear functions over F_p, when evaluated on the Boolean cube. Enroute of constructing our PRG, we prove two structural results for low degree polynomials over finite fields that can be of independent interest. 1) Let f be an n-variate degree d polynomial over F_p. Then, for every ϵ > 0 there exists a subset S ⊂ [n], whose size depends only on d and ϵ, such that Σ_α∈Fpⁿ_{:α≠0,αS=0} |f̂(α)|² ≤ ϵ. 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. 2) Let f be an n-variate degree d polynomial over F_p. If the distribution of f when applied to uniform zero-one bits is ϵ-far (in statistical distance) from its distribution when applied to biased bits, then for every δ > 0, f can be approximated over zero-one bits, up to error δ, by a function of a small number (depending only on ϵ, δ and d) of lower degree polynomials.