ECCC-Report TR07-081https://eccc.weizmann.ac.il/report/2007/081Comments and Revisions published for TR07-081en-usMon, 20 Aug 2007 22:29:31 +0300
Paper TR07-081
| Pseudorandom bits for polynomials |
Andrej Bogdanov,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2007/081We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:
\begin{enumerate}
\item a generator that fools degree-$2$ (i.e., quadratic) polynomials to within error $1/n$, with seed length $s = O(\log n)$,
\item a generator that fools degree-$3$ (i.e., cubic) polynomials to within error $\eps$, with seed length $s = O(\log_{\abs{\F}} n) + f(\eps,\F)$ where $f$ depends only on $\eps$ and $\F$ (not on $n$),
\item assuming the ``Gowers inverse conjecture,'' for every $d$ a generator that fools degree-$d$ polynomials to within error $\eps$, with seed length $s = O(d \cdot \log_{\abs{\F}} n) + f(d,\eps,\F)$ where $f$ depends only on $d,\eps,$ and $\F$ (not on $n$).
\end{enumerate}
We stress that the results in (1) and (2) are unconditional, i.e.~do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove.
Mon, 20 Aug 2007 22:29:31 +0300https://eccc.weizmann.ac.il/report/2007/081