Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-129 | 22nd September 2011 20:41

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


Authors: Eli Ben-Sasson, Ariel Gabizon
Publication: 22nd September 2011 20:43
Downloads: 3416


Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ 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 \ll q$.

More generally, 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$. Then we can extract random bits with error $\epsilon$ from $X$ whenever $q=\Omega(D^2\cdot (p\cdot d)^{6n/k}/\epsilon^2)$. For instance, when $p$, $D$ and the "entropy rate" $n/k$ 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$ 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.

ISSN 1433-8092 | Imprint