The Taub Faculty of Computer Science Events and Talks

Let F be the field of q elements, where q=p^l for prime p. Informally speaking, a polynomial source is a distribution over F^n sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size q assuming p<
For instance, suppose a distribution X over F^n has support size q^k and is sampled by polynomials of individual degree d and total degree D. When p, D and the "entropy rate" k/n are constant, we get an extractor over constant-size fields with constant error. The only previous construction by Dvir, Gabizon and Wigderson required a field of size polynomial in n.

Our proof follows similar lines to that of DeVos and Gabizon on extractors for affine sources, i.e., polynomial sources of degree 1. Our result makes crucial use of a theorem of Hou, Leung and Xiang giving a lower bound on the dimension of products of subspaces. The key insights that enable us to extend these results to the case of polynomial sources of degree greater than 1 are

1) A source with support size q^k must have a linear span of dimension at least k, and in the setting of low-degree polynomial sources it suffices to increase the dimension of this linear span.

2)Distinct Frobenius automorphisms of a (single) low-degree polynomial source are `pseudo-independent' in the following sense: Taking the product of distinct automorphisms (of the very same source) increases the dimension of the linear span of the source.

Joint work with Eli Ben-Sasson