Theory of Computing ------------------- Title : Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic Authors : Eli Ben-Sasson and Ariel Gabizon Volume : 9 Number : 21 Pages : 665-683 URL : http://www.theoryofcomputing.org/articles/v009a021 Abstract -------- A polynomial source of randomness over \$F_q^n\$ is a random variable \$X=f(Z)\$ where \$f\$ is a polynomial map and \$Z\$ is a random variable distributed uniformly over \$F_q^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_q^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_q^n --> \{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).