Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EPS-BIASED:
Reports tagged with eps-biased:
TR07-081 | 10th August 2007
Andrej Bogdanov, Emanuele Viola

Pseudorandom bits for polynomials

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




ISSN 1433-8092 | Imprint