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.