PSEUDORANDOM GENERATORS FOR CC~0[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(logn), for CC~0[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 (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 ε ＞ 0, there exists a subset S C [n], whose size depends only on d and e, such that ∑_(α∈F~n_p:α≠0,α_S=0) |f(α)|~2 ≤ ε. 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.