文章基本信息

标题：Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
本地全文：下载
作者：Shachar Lovett ; Partha Mukhopadhyay ; Amir Shpilka 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper we give the first construction of a pseudorandom generator, with seed length O(logn), for CC0[p], the class of constant-depth circuits with unbounded fan-in MODp gates, for some prime p . More accurately, the seed length of our generator is O(logn) for any constant error 0. In fact, we obtain our generator by fooling distributions generated by low degree polynomials, over Fp, when evaluated on the Boolean cube.This result significantly extends previous constructions that either required a long seed [LVW93] or that could only fool the distribution generated by linear functions over Fp, when evaluated on the Boolean cube [LRTV09,MZ09]. 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 Fp.Then, for every 0 there exists a subset S[n] , whose size depends only on d and , such that Fnp:=0S=0f()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 Fp.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, up to error , by a function of a small number (depending only on and d) of lower degree polynomials.
关键词：CC_0[p], low-degree polynomials, Pseudorandomness