×

Extractors for polynomials sources over constant-size fields of small characteristic. (English) Zbl 1357.68147

Gupta, Anupam (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 15th international workshop, APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge, MA, USA, August 15–17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32511-3/pbk). Lecture Notes in Computer Science 7408, 399-410 (2012).
Summary: A polynomial source of randomness over \(\mathbb F_q^n\) is a random variable \(X = f(Z)\) where \(f\) is a polynomial map and \(Z\) is a random variable distributed uniformly on \(\mathbb F_q^r\) for some integer \(r\). The three main parameters of interest associated with a polynomial source are the field size \(q\), the (total) degree \(D\) of the map \(f\), and the “rate” \(k\) which specifies how many different values does the random variable \(X\) take, where rate \(k\) means \(X\) is supported on at least \(q ^{k }\) different values. For simplicity we call \(X\) a \((q,D,k)\)-source.
Informally, an extractor for \((q,D,k)\)-sources is a deterministic function \(E:\mathbb F_q^n\to \left \{{0,1} \right \}^m\) such that the distribution of the random variable \(E(X)\) is close to uniform on \(\left \{{0,1} \right \}^m\) for any \((q,D,k)\)-source \(X\). Generally speaking, the problem of constructing deterministic extractors for such sources becomes harder as \(q\) and \(k\) decrease and as \(D\) grows larger.
The only previous work of Z. Dvir et al. [Comput. Complexity 18, No. 1, 1–58 (2009; Zbl 1210.68136) (Extended abstract appeared in FOCS 2007)] construct extractors for such sources when \(q \gg n\). In particular, even for \(D = 2\) no constructions were known for any fixed finite field.
In this work we construct for the first time extractors for \((q,D,k)\)-sources for constant-size fields. Our proof builds on the work of M. DeVos and A. Gabizon, “Simple affine extractors using dimension expansion.” In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, p. 63 (2010)] on extractors for affine sources, with two notable additions (described below). Like the DeVos–Gabizon paper, our result makes crucial use of a theorem of Hou, Leung and Xiang [X.-D. Hou et al., J. Number Theory 97, No. 1, 1–9 (2002; Zbl 1034.11020)] 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 \(D\) 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.
For the entire collection see [Zbl 1248.68036].

MSC:

68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
11T23 Exponential sums
12E20 Finite fields (field-theoretic aspects)
60E15 Inequalities; stochastic orderings
PDFBibTeX XMLCite
Full Text: DOI