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 ({mathbb{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 ({mathbb{F}_p}) , when evaluated on the Boolean cube (Lovett et al. 2009; Meka & Zuckerman 2009).