ECCC-Report TR08-042https://eccc.weizmann.ac.il/report/2008/042Comments and Revisions published for TR08-042en-usSat, 12 Apr 2008 11:05:11 +0300
Paper TR08-042
| Deterministic Extractors for Algebraic Sources |
Zeev Dvir
https://eccc.weizmann.ac.il/report/2008/042An 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.
Sat, 12 Apr 2008 11:05:11 +0300https://eccc.weizmann.ac.il/report/2008/042