A polynomial source of randomness over $\F^n$ is a random variable $X=f(Z)$ where $f$ is a polynomial map and $Z$ is a random variable distributed uniformly over $\F^r$ for some integer $r$. The three main parameters of interest associated with a polynomial source are the order $q$ of the field, the (total) degree $D$ of the map $f$, and the base-$q$ logarithm of the size of the range of $f$ over inputs in $\F^r$, denoted by $k$. For simplicity we call $X$ a $(q,D,k)$-source.

Informally, an extractor for $(q,D,k)$-sources is a function $E:\F^n\to \{0,1\}^m$ such that the distribution of the random variable $E(X)$ is close to uniform over $\{0,1\}^m$ for any $(q,D,k)$-source $X$. Generally speaking, the problem of constructing extractors for such sources becomes harder as $q$ and $k$ decrease and as $D$ increases. A rather large number of recent works in the area of derandomization have dealt with the problem of constructing extractors for $(q,1,k)$-sources, also known as “affine” sources. Constructing an extractor for non-affine sources, i.e., for $D>1$, is a much harder problem. Prior to the present work, only one construction was known, and that construction works only for fields of order much larger than $n$ (Dvir et al., CCC 2009). In particular, even for $D=2$, no construction was known for any fixed finite field. In this work we construct extractors for $(q,D,k)$-sources for fields of constant order. Our proof builds on the work of DeVos and Gabizon (CCC 2010) on extractors for affine sources. Like the DeVos--Gabizon paper, our result makes crucial use of a theorem of Hou, Leung and Xiang (J. Number Theory 2002) which gives a lower bound on the dimension of products of subspaces.

A conference version of this paper appeared in the Proceedings of the 16th Internat. Workshop on Randomization and Computation (RANDOM'12).