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       : https://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).