TR07-081 Authors: Andrej Bogdanov, Emanuele Viola

Publication: 20th August 2007 22:29

Downloads: 3917

Keywords:

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.