Name
Title | ||
|---|---|---|
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields |
Abstract | ||
|---|---|---|
In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}^0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon0$. In fact, we obtain our generator by fooling distributions generated by low degree polynomials, over $\mathbb{F}_p$, {\em 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 $\mathbb{F}_p$, 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 $\mathbb{F}_p$. Then, for every $\epsilon0$ 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 \ne 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 $\delta0$, $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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00037-012-0051-7 | Foundations of Computer Science |
Keywords | Field | DocType |
pseudorandom generator,finite field,low-degree polynomial,fourier spectrum | Prime (order theory),Discrete mathematics,Binary logarithm,Pseudorandom generators for polynomials,Combinatorics,Finite field,Polynomial,Pseudorandom generator,Mathematics,Pseudorandom number generator,Cube | Journal |
Volume | Issue | ISSN |
22 | 4 | 0272-5428 |
ISBN | Citations | PageRank |
978-1-4244-8525-3 | 3 | 0.41 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shachar Lovett | 1 | 520 | 55.02 |
| Partha Mukhopadhyay | 2 | 91 | 12.71 |
| Amir Shpilka | 3 | 1095 | 64.27 |