Deterministic Extractors for Algebraic Sources
Zeev Dvir · 2008
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.