Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-042 | 6th April 2008 00:00

Deterministic Extractors for Algebraic Sources


Authors: Zeev Dvir
Publication: 12th April 2008 11:05
Downloads: 1622


An algebraic source is a random variable distributed
uniformly over the set of common zeros of one or more multivariate
polynomials defined over a finite field $F$. Our main result is
the construction of an explicit deterministic extractor for
algebraic sources over exponentially large prime fields. More
precisely, we give an explicit (and arguably simple) function $E :
F^n --> {0,1}^m$ such that the output of $E$ on any
algebraic source in $F^n$ is close to the uniform distribution,
provided that the degrees of the defining polynomials are not too
high and that the algebraic source contains `enough' points. This
extends previous works on extraction from affine sources
(sources distributed over subspaces) and from polynomial
sources (sources defined as the image of a low degree
polynomial mapping).

We also give an additional construction of a deterministic
extractor for algebraic sources with support larger than
$|F|^{n/2}$. This construction works over fields as small as
$d^O(1)$, where $d$ is the maximal degree of a polynomial used
to define the source.

ISSN 1433-8092 | Imprint