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 CC0[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 epsilon > 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 (Luby et al. 1993) or could only fool the distribution generated by linear functions over F-p, when evaluated on the Boolean cube (Lovett et al. 2009; Meka & Zuckerman 2009). En route 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 epsilon > 0, there exists a subset S subset of [n], whose size depends only on d and epsilon, such that Sigma(alpha is an element of Fpn:alpha not equal 0, alpha S=0) broken vertical bar(f) over cap(alpha)broken vertical bar(2)   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.
pseudorandom generators low-degree polynomials small-depth circuits