Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR07-081 | 10th August 2007 00:00

#### Pseudorandom bits for polynomials

TR07-081
Authors: Andrej Bogdanov, Emanuele Viola
Publication: 20th August 2007 22:29
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