Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
复制标题
CC0[p] 的伪随机生成器和有限域上低次多项式的傅里叶谱
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Amir Shpilka
中科院分区：
文献类型：
--
作者：
Shachar Lovett;P. Mukhopadhyay;Amir Shpilka
在本文中，我们为CC0 [P]进行了第一个具有种子长度O（log n）的伪随机发电机的结构，该类别的恒定深度电路具有无界的扇形扇形，用于一些prime p准确地说，对于任何常数错误$$ {epsilon> 0} $$，我们的发电机的种子长度实际上是O（log n）。 {f} _p} $$，当在布尔立方体上进行评估时。在布尔立方体上进行评估（Lovett等，2009； Meka＆Zuckerman 2009）。可能具有独立兴趣的字段。1。let f是$$ {mathbb {f} _p} $$的n variate d polyenmial d。子集$$ {s subset [n]} $$，其大小仅取决于d and $$ {epsilon} $$，因此$$ {sum_ {sum_ {mathbb {f} _p^n：alpha
e 0，alpha_s = 0} | hat {f}（alpha）|^2 leq epsilon} $$。 S很小。2。 - 应用于其分布时的far（以统计距离为单位）对于有偏见的位，然后在每$$ {delta> 0} $$的情况下，f可以通过少量的函数近似零 - 一个位，最多Δ（仅取决于$$ {Epsilon，delta}}低度多项式的$$和d）。
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 MODp 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). 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 $${mathbb{F}_p}$$ . Then, for every $${epsilon > 0}$$ , there exists a subset $${S subset [n]}$$ , whose size depends only on d and $${epsilon}$$ , such that $${sum_{alpha in mathbb{F}_p^n: alpha
e 0, alpha_S=0}|hat{f}(alpha)|^2 leq epsilon}$$ . 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 $${mathbb{F}_p}$$ . If the distribution of f when applied to uniform zero–one bits is $${epsilon}$$ -far (in statistical distance) from its distribution when applied to biased bits, then for every $${delta > 0}$$ , f can be approximated over zero–one bits, up to error δ, by a function of a small number (depending only on $${epsilon,delta}$$ and d) of lower degree polynomials.