Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-081 | 10th August 2007 00:00

Pseudorandom bits for polynomials

RSS-Feed




TR07-081
Authors: Andrej Bogdanov, Emanuele Viola
Publication: 20th August 2007 22:29
Downloads: 3920
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint