Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic

摘要

Let F be the field of q elements, where q=p for prime p. Informally speaking, a polynomial source is a distribution over Fn sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size q assuming pq.More generally, suppose a distribution X over Fn has support size qk and is sampled by polynomials of individual degree d and total degree D. Then we can extract random bits with error from X whenever q=(D2(pd)6nk2) . For instance, when p, D and the "entropy rate" nk are constant, we get an extractor over constant-size fields with constant error. The only previous construction by [Dvir, Gabizon and Wigderson, FOCS 2007] required a field of size polynomial in n.Our proof follows similar lines to that of [DeVos and Gabizon, CCC 2010] 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, J. Number Theory 2002] 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 are1) A source with support size qk 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.