Ariel Gabizon (CS. Technion)
Wednesday, 16.5.2012, 12:30
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