Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic

摘要

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^no {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 theProceedings of the 16th Internat. Workshop on Randomizationand Computation (RANDOM'12).