__
TR08-042 | 6th April 2008 00:00
__

#### Deterministic Extractors for Algebraic Sources

TR08-042
Authors:

Zeev Dvir
Publication: 12th April 2008 11:05

Downloads: 4422

Keywords:

**Abstract:**
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.