Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 9 (2013) Article 21 pp. 665-683
APPROX-RANDOM 2012 Special Issue
Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic
Received: November 13, 2012
Revised: May 12, 2013
Published: July 19, 2013
Download article from ToC site:
[PDF (272K)] [PS (1038K)] [Source ZIP]
Keywords: explicit construction, extractors, field extension, polynomials, polynomials - multivariate, Frobenius automorphisms, character sums
ACM Classification: F.0, G.2.0, G.3
AMS Classification: 11T06,11T23,12F05

Abstract: [Plain Text Version]

\newcommand{\F}{\mathbb F_q}

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).