Authors Eli Ben-Sasson, Ariel Gabizon,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2012
Extractors for Polynomial Sources over
Fields of Constant Order and Small
Characteristic∗
Eli Ben-Sasson† Ariel Gabizon‡
Received November 13, 2012; Revised May 12, 2013; Published July 19, 2013
Abstract: A polynomial source of randomness over Fnq is a random variable X = f (Z)
where f is a polynomial map and Z is a random variable distributed uniformly over Frq for
some integer r. The three main parameters of interest associated with a polynomial source
are the order q of the field, the (total) degree D of the map f , and the base-q logarithm
of the size of the range of f over inputs in Frq , denoted by k. For simplicity we call X a
(q, D, k)-source.
Informally, an extractor for (q, D, k)-sources is a function E : Fnq → {0, 1}m such that the
distribution of the random variable E(X) is close to uniform over {0, 1}m for any (q, D, k)-
source X. Generally speaking, the problem of constructing extractors for such sources
becomes harder as q and k decrease and as D increases. A rather large number of recent
∗ A conference version of this paper appeared in the Proceedings of RANDOM 2012 [1].
† Supported by funding from the European Community’s Seventh Framework Programme (FP7/2007-2013) under grant
agreement number 240258.
‡ Supported by funding from the European Community’s Seventh Framework Programme (FP7/2007-2013) under grant
agreement number 240258.
ACM Classification: F.0, G.2.0, G.3
AMS Classification: 11T06, 11T23, 12F05
Key words and phrases: explicit construction, extractors, field extension, polynomials, polynomials -
multivariate, Frobenius automorphisms, character sums
© 2013 Eli Ben-Sasson and Ariel Gabizon
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a021
E LI B EN -S ASSON AND A RIEL G ABIZON
works in the area of derandomization have dealt with the problem of constructing extractors
for (q, 1, k)-sources, also known as “affine” sources. Constructing an extractor for non-affine
sources, i. e., for D > 1, is a much harder problem. Prior to the present work, only one
construction was known, and that construction works only for fields of order much larger
than n (Dvir et al., CCC 2009). In particular, even for D = 2, no construction was known
for any fixed finite field. In this work we construct extractors for (q, D, k)-sources for fields
of constant order. Our proof builds on the work of DeVos and Gabizon (CCC 2010) on
extractors for affine sources. Like the DeVos–Gabizon paper, our result makes crucial use of
a theorem of Hou, Leung and Xiang (J. Number Theory 2002) which gives a lower bound on
the dimension of products of subspaces.
1 Introduction
This paper is part of a long and active line of research devoted to the problem of “randomness extraction”:
Given a family of distributions all guaranteed to have a certain structure, devise a method that can convert
a sample from any distribution in this family to a sequence of uniformly distributed bits—or at least a
sequence statistically close to the uniform distribution. Usually, it is easy to prove that a random function
is, with high probability, a good extractor for the given family, and the challenge is to give an explicit
construction of such an extractor.
The first example of a randomness extraction problem was given by von Neumann [24], who gave an
elegant solution1 to the following problem: How can a biased coin with unknown bias be used to generate
“fair” coin tosses? In this case the input distribution consists of independent identically distributed bits
which makes the extraction task simpler. Since then many families of more complex distributions have
been studied. Also, the concept of randomness extraction has proven to be useful for various applications.
The reader is referred to the introduction of [10] for more details on the classes of distributions studied,
references and motivation.
We now give a formal definition of extractors and related objects called dispersers.
Definition 1.1 (Extractors and dispersers). Let Γ and Ω be some finite domains. Let C be a class of
random variables taking values in Γ. We say a random variable P taking values in Ω is ε-close to uniform
if for every A ⊆ Ω,
|A|
Pr(P ∈ A) − ≤ε.
|Ω|
• Fix any 0 ≤ ε < 1. A function E : Γ → Ω is an ε-extractor for C if for every X ∈ C, the random
variable E(X) is ε-close to uniform.
• A function D : Γ → Ω is a disperser for C if for every X ∈ C, the random variable D(X) takes more
than one value in Ω with nonzero probability.
1 Von Neumann’s algorithm as usually described does not precisely fit into the formal definition of a randomness extractor, as
the algorithm is allowed not to produce an output.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 666
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
1.1 Polynomial sources
In this paper we construct extractors for polynomial sources, which are distributions that are sampled
by applying low-degree polynomials to uniform inputs as defined next. Throughout this paper, if Ω is a
finite set, we let UΩ denote the uniform distribution over Ω. By the individual degree of a multivariate
polynomial f we mean the smallest d such that f has degree ≤ d in each variable.
Definition 1.2 (Polynomial sources). Fix integers n, k, d with k ≤ n and a field Fq . We define M[n, k, d]
to be the set of mappings f : Frq → Fnq , where r is an integer counting the number of inputs to the source
and
f (Z1 , . . . , Zr ) = ( f1 (Z1 , . . . , Zr ), . . . , fn (Z1 , . . . , Zr ))
such that
• for every i ∈ [n], fi is a polynomial in Fq [Z1 , . . . , Zr ] of individual degree at most d.
• The range of f is of size at least qk . Formally,
|{ f (z1 , . . . , zr ) | (z1 , . . . , zr ) ∈ Frq }| ≥ qk .
A (n, k, d)-polynomial source is a random variable of the form f (UFrq ) for some and f ∈ M[n, k, d] with r
inputs. (When the parameters n, k, d are clear from the context, we shall omit them, and simply use the
term “polynomial source.”)
Definition 1.3 (Polynomial-source extractors). Let Ω be some finite set. A function E : Fnq → Ω is a
(k, d, D, ε)-polynomial source extractor if for every f ∈ M[n, k, d] of total degree at most D and r inputs,
E( f (UFrq )) is ε-close to uniform (where UFrq denotes the uniform distribution over Frq ).
Remark 1.4. A few words are in order regarding Definition 1.2.
• The number of inputs used by our source, denoted by r in Definition 1.2, does not affect the
parameters of our extractors, and hence we omit this parameter from the definition of polynomial
sources and extractors.
• In the context of extractors what might have seemed more natural is to require the random variable
f (UFrq ) to have min-entropy2 at least k · log q. Our requirement on the size of the range of f is
seemingly weaker, and suffices for our construction to work. (In particular, our result implies that,
for some settings of field order and degree, when f has large range the random variable f (UFrq ) is
statistically close to a random variable that has at least a certain min-entropy.)
• Individual degree plays a larger role than total degree in our results. In fact, the first stage of our
construction—constructing a non-constant polynomial over Fq —requires a field of order depending
only on individual degree. This is why it is more convenient to limit individual degree and not total
degree in the definition of M[n, k, d].
2 The min-entropy of a random variable X is the largest real number ` such that for every value x we have Pr(X = x) ≤ 2−` .
This is the standard measure of randomness in the context of extractors, originating from Chor and Goldreich [7].
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 667
E LI B EN -S ASSON AND A RIEL G ABIZON
Motivation To motivate our study of extractors for polynomial sources, we mention four distinct
applications of such extractors for the simplest class of sources: affine ones, in which the degree of
the source is 1 (see definition below). Demenkov and Kulikov [9] showed, using elementary methods,
that any circuit over the full binary basis that computes an affine disperser for min-entropy rate o(1)
must contain at least 3n(1 − o(1)) gates, and this matches the previous best circuit lower bound of Blum
from 1984 [4]. Another application of affine extractors was given by Viola [23] and independently
by De and Watson [8] showing how to use them to construct extractors for bounded depth circuits. A
third application was given by Ben-Sasson and Zewi [27] who showed how to construct two-source
extractors and bipartite Ramsey graphs from affine extractors. Recent work of Guruswami [15] and of
Dvir and Lovett [13] use “subspace evasive functions” which are closely related to affine extractors to get
better algorithms for list-decoding of folded Reed-Solomon codes. These applications lead us to believe
that extractors for general low-degree sources of the kind defined next will similarly be useful in other
branches of computational complexity theory.
1.2 Previous work and our result
Polynomial-source extractors are a generalization of affine source extractors where the source is sampled
by a degree-one map. There has been much work recently on affine-source extractors [2, 5, 26, 14, 10, 17]
and related objects called affine-source dispersers [3, 22] where the output is required to be non-constant
but not necessarily close to uniform.
Turning to extractors for non-affine, low-degree sources, the only previous work is by Dvir, Gabizon
and Wigderson [12], and it requires large fields. In particular, to extract a single bit [12] needs a field of
order at least nc where c > 1 is a constant and n is number of inputs to the extractor, i. e., the number of
outputs of the polynomial source.
(In a related albeit different vein, Dvir [11] constructed extractors for distributions that are uniform
over low-degree algebraic varieties, which are sets of common zeros of a system of low-degree multivariate
polynomials.)
In this work we construct polynomial-source extractors over much smaller fields than previously
known, assuming the characteristic of the field is significantly smaller than the order of the field.
Theorem 1.5 (Main–Extractor). Fix a field Fq of characteristic p, integers d, D, 4 ≤ k ≤ n where n ≥ 25,
and a positive integer m < 1/2 · log p q. Let α = 3D · (p · d)3n/k . Assume that q ≥ 2 · α 2 . There is an
explicit (k, d, D, ε)-polynomial source extractor E : Fnq → Fmp with error ε = pm/2 · α · q−1/2 .
In particular, when D, n/k, and p are constant, we get a polynomial-source extractor for fields of
bounded order. We state such an instantiation.
Corollary 1.6 (Extractor for quadratic sources of min-entropy rate half over fields of characteristic 2).
There is a universal constant C such that the following holds. For any ε > 0 and any q > C/ε 2 which is a
power of 2, there is an explicit (n/2, 2, 2, ε)-polynomial source extractor E : Fnq → {0, 1}.
Non-Boolean dispersers for smaller fields Along the way to our proof we construct a weaker object
called a non-Boolean disperser.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 668
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
A non-Boolean disperser maps the source into a relatively small (but not {0, 1}) domain and guarantees
the output is non-constant. The advantage of this part of the construction is that it works for smaller
fields than the extractor, and moreover, the field order for which it works depends only on the individual
degrees of the source polynomials. In the theorem and corollary below we use an implicit isomorphism
of Fnq and Fqn . See an explanation of this in the beginning at the beginning of Section 3.
Theorem 1.7 (Main–Disperser). Fix a prime power q = p` . Fix integers k ≤ n and d < s such that n is
prime and s is a power of p. Fix a non-trivial Fq -linear map T : Fnq → Fq . Let u = d(n − k)/(k − 1)e.
2 u
Define P : Fnq → Fq by P(x) , T (x1+s+s +···+s ). Assume that q > d · (su+1 − 1)/(s − 1). Then, for any
f (Z) = f (Z1 , . . . , Zr ) ∈ M[n, k, d], P( f (Z)) is a non-constant function from Frq into Fq .
We instantiate this result for F4 which is the smallest field for which it works.
Corollary 1.8 (Disperser for min-entropy rate half over F4 ). Let n be prime. Define the function
P : Fn4 → F4 as follows. Think of the input x as an element of F4n and compute x3 . Now output the first
coordinate of the vector x3 . Then for any f ∈ M[n, dn/2 + 1e, 1] (i. e., any multilinear f ∈ F4n [Z1 , . . . , Zr ]
that has range of size at least 4dn/2+1e ) the polynomial P( f (Z1 , . . . , Zr )) is a non-constant function from
Fr4 into F4 .
Proof. We use Theorem 1.7, setting k = dn/2 + 1e, q = 4, d = 1, s = 2 and T : Fn4 → F4 to be the map
that projects to the first coordinate. This gives u = 1, and thus P(x) = T (x3 ) in this case.
2 Overview of the proof
Our goal is to describe an explicit function E : Fnq → {0, 1}m such that for any (n, k, d)-polynomial source
X we have that E(X) is ε-close to the uniform distribution over {0, 1}m . We do this in two steps.
First we construct a function E0 , called a non-Boolean disperser, that is guaranteed to be non-constant
on X, i. e., such that the random variable Y = E0 (X) takes more than one value. This part is done in
Section 4. Then we apply a second function E1 to the output of E0 and prove, using the fact that E0
is a low-degree function in our case, that the distribution of E1 (Y ) = E1 (E0 (X)) is ε-close to uniform.
This “disperser–to–extractor” part is described in Sections 5 and 6. We now informally describe the
two functions assuming for simplicity that the field Fq is of characteristic 2 and that n is prime. Before
starting let us recall the notion of a Frobenius automorphism. If K is a finite field of characteristic 2 then
the mapping
i
σi : K → K, σi (z) = z2
is a Frobenius automorphism of K over F2 .
The three elementary properties of this mapping that we use below are
(i) its F2 -linearity: σi (a + b) = σi (a) + σi (b),
(ii) its distinctness: if K is an extension of F2 of degree at least t and 0 ≤ i < j ≤ t − 1 then σi and σ j
are different, and
(iii) its dimension-preservation: If K ⊃ Fq ⊃ F2 then A ⊂ K and σi (A) , {σi (a) | a ∈ A} span spaces
of equal dimension over Fq (see Claim 3.8).
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 669
E LI B EN -S ASSON AND A RIEL G ABIZON
A different view of low-degree sources The first part of our analysis uses a somewhat nonstandard
view of low-degree sources that we need to highlight. The random variable X ranges over Fnq and is the
output of n degree-d polynomials over Fq . Let
F≤d
q [Z1 , . . . , Zr ]
denote the set of monomials over Fq of individual degree at most d where d < q. (We use Z variables to
denote inputs of the polynomial source and X variables for its output.) Suppose the i-th coordinate of X is
(i)
Xi = P(i) (Z1 , . . . , Zr ) = ∑ aM · M(Z1 , . . . , Zr )
M∈F≤d
q [Z1 ,...,Zr ]
(i)
where aM ∈ Fq and Z1 , . . . , Zr are independent random variables distributed uniformly over Fq . Applying
(1) (n)
an Fq -linear bijection φ : Fnq → Fqn , let aM = φ (aM , . . . , aM ) denote the sequence of coefficients of the
monomials M, viewed now as a single element in Fqn . Our nonstandard view is that our source is
X = P(Z1 , . . . , Zr ) = aM · M(Z1 , . . . , Zr )
∑ (2.1)
M∈F≤d
q [Z1 ,...,Zr ]
where the coefficients aM and the random variable X come from the “large” field Fqn but the random
variables Z1 , . . . , Zr still range over the “small” field Fq . This large-field-small-field view will be important
in what comes next. In particular, we shall use the following claim which reduces the problem of
constructing a non-Boolean disperser to that of constructing a polynomial whose coefficients span Fqn
over Fq .
Claim 2.1 (Full-span polynomials are non-constant coordinate-wise). Suppose P has individual degree
smaller than q. If the set of coefficients A = {aM | deg(M) > 0} appearing in (2.1) spans Fqn over Fq
then Xi = P(i) (Z1 , . . . , Zr ) is a non-constant function on Frq for every i ∈ {1, . . . , n}.
Proof. By way of contradiction. If P(i) is constant on Frq and has individual degrees smaller than q, then
as a formal polynomial it is constant. This implies that all elements of A, as vectors in Fnq , are equal to
zero in the i-th coordinate. Thus, A spans a strict subspace of Fqn in contradiction to the assumption of
the claim.
Non-Boolean disperser We start with the simplest nontrivial case to which our techniques apply and
construct a non-Boolean disperser for homogeneous multilinear quadratic sources with min-entropy rate
greater than half over the finite field with 4 elements (this is a special case of Corollary 1.8). Using [r]
2
to denote the set {(i, j) | 1 ≤ i < j ≤ r} and writing X as in (2.1) we get
X= ∑ ai j Zi Z j , ai j ∈ F4n (2.2)
(i, j)∈(2r )
where Z1 , . . . , Zr are uniformly and independently distributed over F4 and X takes more than 4n/2 distinct
values. Let
[r]
A = ai j (i, j) ∈ (2.3)
2
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 670
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
denote the set of coefficients appearing in (2.2). In light of Claim 2.1 it suffices to construct E0 such
that E0 (X), when written as a polynomial over Z1 , . . . , Zr , has a set of coefficients that spans F4n over
F4 . (Then we “project” this polynomial onto, say, the first coordinate and get a non-constant function
mapping into F4 , i. e., a non-Boolean disperser.)
To do this we take the approach of DeVos and Gabizon [10] which uses the theorem of Hou, Leung
and Xiang [16]. Assuming n is prime, this theorem implies that if A, B ⊂ Fqn are sets spanning spaces of
respective dimensions d1 , d2 over Fq , then the set of products
A · B , {a · b | a ∈ A, b ∈ B}
spans a subspace of Fqn over Fq of dimension at least min{n, d1 + d2 − 1}. Returning to our case and
taking A as in (2.3), our first observation is that dim(span(A)) > n/2 because X is contained in span(A).
So the theorem of [16] mentioned above implies that span(A · A) = F4n . Consider what would happen
if we could sample twice from X independently and take the product of the two samples in F4n . Using
X 0 , Z10 , . . . , Zr0 to express the second sample we write this product as
X · X0 = ∑ ai j Zi Z j · ∑ ai j Zi0 Z 0j . 0 0
(i, j)∈(2r ) (i0 , j0 )∈(2r )
Opening the right-hand-side as a polynomial in Z1 , . . . , Zr , Z10 , . . . , Zr0 we see that its set of coefficients is
A · A which spans F4n over F4 , as desired.3
Unfortunately we only have access to a single sample of X and have to make use of it. We use the fact
that F4 is a degree 2 extension of a smaller field (F2 ) and hence has two distinct Frobenius automorphisms.
And here comes our second observation: Taking the product of 2 distinct Frobenius automorphisms of a
single sample of X has a similar effect to that of taking two independent samples of X! Indeed, take the
product of σ0 (X) and σ1 (X) and, using the linearity of Frobenius mapping, expand as
X · X2 = ∑ ai j Zi Z j · ∑ a2i j Zi2 Z 2j
(i, j)∈(2r ) (i0 , j0 )∈(2r )
= ∑ ai j a2i j Zi Z j Zi2 Z 2j .
0 0 0 0
(i, j),(i0 , j0 )∈(2r )
The main point is that every element in the set of products of A and A2 , a2 | a ∈ A appears as
the coefficient of a monomial in the polynomial above and these monomials are distinct over F4 . And
the dimension-preservation of σ1 implies that dim(span(A2 )) = dim(span(A)) > n/2. Consequently, the
theorem of [16] implies that A · A2 spans F4n over F4 , so by Claim 2.1 the function E0 (X), which outputs
the first coordinate of X · X 2 , is non-constant for X and this completes the sketch of our non-Boolean
disperser for the special case of homogenous, quadratic, multilinear polynomials over F4 .
3 The same argument would work as well over the two-element field F . The extension field is needed to deal with the case
2
of a single source as explained next.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 671
E LI B EN -S ASSON AND A RIEL G ABIZON
To extend this argument to general polynomial sources of individual degree ≤ d we carefully select a
set of t distinct Frobenius automorphisms σi0 , . . . , σit−1 (assuming Fq is an extension-field of degree at
least t) such that the mapping f : (F≤d t
q [Z1 , . . . , Zr ]) → Fq [Z1 , . . . , Zr ] given by
t−1
f (M0 , . . . , Mt−1 ) = ∏ σi j (M j ) mod (Z1q − Z1 , . . . , Zrq − Zr )
j=0
is injective. Then we argue, just as in the case above, that the function g(X) , ∏t−1
j=0 σi j (X) expands to a
sum of distinct monomials with coefficients ranging over the product set  = σi0 (A) · · · σit−1 (A) where
σ (A) = {σ (a) | a ∈ A}. The theorem of [16] is applied t times to conclude that  spans Fqn over Fq . Now
we apply Claim 2.1 and get that the first coordinate of g(X) (viewing g(X) as a tuple of n polynomials
over Fq ) is a non-constant function. Details are provided in Section 4.
From dispersers to extractors This part is based on the work of Gabizon and Raz [14] and uses an
important theorem of Weil [25]. This theorem implies the following. Suppose we evaluate a polynomial
√
g ∈ Fq [Z1 , . . . , Zr ] of small-enough degree deg(g) < q on a uniformly random sample in Frq and then take
the first bit of this evaluation (when viewing it as a vector over F2 ). Then, this bit will either be constant
(in which case we then say that g is “degenerate,” or close to the uniform distribution. Assuming our
√
source is low-degree and the order q of the field is sufficiently large, we can argue that deg(E0 (X)) < q
because X is low-degree by assumption and E0 is low-degree by construction. So to apply Weil’s Theorem
and get an extractor we only need to ensure that we have in hand a non-degenerate polynomial. Alas,
we have relatively little control over the polynomial source so we need to transform it somehow into
a non-degenerate one in a black-box manner. Here we apply another observation, proved by Swastik
Kopparty, which says that (E0 (X))v is non-degenerate for odd4 v > 2. This part is explained in Section 5.
So we take E1 (Y ) to be the first5 bit of Y 3 and using this observation and Weil’s Theorem conclude that
E1 (E0 (X)) is close to uniform. Analysis of the resulting extractor is given in the appendix.
3 Preliminaries
Notation: When we discuss identities between polynomials we only mean identities as formal polyno-
mials. We will frequently alternate between viewing x ∈ Fnq as an element of either Fnq or the field Fqn .
When we do this we assume it is using an implicit bijective map φ : Fnq → Fqn that is an isomorphism of
vector spaces. That is, φ (t1 · a1 + t2 · a2 ) = t1 · φ (a1 ) + t2 · φ (a2 ) for any t1 ,t2 ∈ Fq and a1 , a2 ∈ Fnq . Such
φ is efficiently computable using standard representations of Fqn . (For details see for example the book
of Lidl and Niederreiter [18].) For a set Ω we denote by UΩ the uniform distribution over Ω.
3.1 Weil bounds for additive character sums
The seminal work of Weil [25] on the “Riemann hypothesis for curves over finite fields” implies very
useful bounds on character sums. As we will see in this section, these bounds enable us to extract
4 For characteristic p > 2 the criteria for v is a bit different: we need p - v.
5 In fact, we can output several bits. See Section 3.1 for details.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 672
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
randomness from certain “low-degree distributions.”
For background on characters of finite fields see [21] or Section 3.2 of [14]. The following version of
the Weil bound was proved by Carlitz and Uchiyama [6].
Theorem 3.1 (Weil-Carlitz-Uchiyama bound). Let q = p` for prime p and an integer `. Let ψ be a
non-trivial additive character of Fq (that is, not identically 1). Let f (Z) be a polynomial in Fq [Z] of
degree d. Suppose that f is not of the form h p + h + c for any h ∈ Fq [Z] and c ∈ Fq . Then
∑ ψ( f (z)) ≤ (d − 1) · q1/2 .
z∈Fq
We require the following generalization of Vazirani’s XOR Lemma from Rao [20], appearing there as
Lemma 4.2.
Lemma 3.2 (Rao’s XOR lemma). Let X be a distribution
p on a finite abelian group G s.t. |E(ψ(X))| ≤ ε
for any non-trivial character ψ of G. Then X is ε · |G|-close to uniform on G.
The above lemma implies it suffices to bound additive character sums of a distribution over Fq in
order to extract randomness. This is formalized in Lemma 3.4 below. To state the lemma we first define
how to extract a few entries of an element in F p` .
Definition 3.3 (Prefix projection). Let q = p` for prime p and an integer `. Fix an isomorphism between
Fq and F`p and view x ∈ Fq as (x1 , . . . , x` ) ∈ F`p . Fix an integer m ≤ `. We define the prefix projection
function Em : Fq → Fmp by Em (x) = Em ((x1 , . . . , x` )) , (x1 , . . . , xm ).
Lemma 3.4 (XOR lemma for prefix projections). Let q = p` for prime p and an integer `. Let X be a
distribution on Fq such that |E(ψ(X))| ≤ ε for any non-trivial additive character ψ of Fq . Then Em (X)
is pm/2 · ε-close to uniform.
Proof. We claim that a function of the form ψ 0 (a) , ψ(Em (a)) where ψ is a character of Fmp , is a
character of Fq : Let ω ∈ C be a primitive p-th root of unity. The additive characters of Fq are exactly the
functions ψ : Fq → C of the form ψ(a) = ω T (a) where T : Fq → F p is an F p -linear function and T (a) is
interpreted as an integer in {0, . . . , p − 1}. In particular, this includes such functions where T only looks
at the first m coordinates of a (recall that we identify Fq with F`p ); and such functions in turn, are exactly
those of the form ψ(Em (a)) where ψ is a character of Fmp . Hence, from the assumption of the lemma
|E(ψ(Em (X)))| ≤ ε for any non-trivial additive character of Fmp . From Lemma 3.2, we have that Em (X)
is pm/2 · ε-close to uniform.
Summing up the previous results we reach the statement that will be later used in analyzing our
extractors.
Corollary 3.5 (Weil-Carlitz-Uchiyama for prefix projections). Let q = p` for prime p and an integer `.
Let f (Z) be a polynomial in Fq [Z] of degree d. Suppose that f is not of the form h(Z) p + h(Z) + c for any
√
h(Z) ∈ Fq [Z] and c ∈ Fq . Then Em ( f (UFq )) is pm/2 · d/ q-close to uniform.
Proof. Follows immediately from Theorem 3.1 and Lemma 3.4.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 673
E LI B EN -S ASSON AND A RIEL G ABIZON
3.2 Dimension expansion of products
Recall that Fqn is a vector space over Fq isomorphic to Fnq . For a set A ⊆ Fqn we denote by dim(A) the
dimension of the Fq -span of A. For sets A, B ⊆ Fqn let
A · B , {a · b | a ∈ A, b ∈ B} .
Hou, Leung and Xiang [16] show that such products expand in dimension. The following theorem is a
corollary of Theorem 2.4 of [16].
Theorem 3.6 (Dimension expansion of products). Let Fq be any field, and let n be prime.6 Let A and B
be non-empty subsets of Fqn such that A, B 6= {0}. Then
dim(A · B) ≥ min{n, dim(A) + dim(B) − 1} .
In particular, if A1 , . . . , Am are non-empty subsets of Fqn such that for all 1 ≤ i ≤ m, dim(Ai ) ≥ k for some
k ≥ 1. Then
dim(A1 · · · Am ) ≥ min{n, k · m − (m − 1)} .
Remark 3.7. The definition of A · B is somewhat different from that in [16] where it is defined only for
subspaces, and as the span of all possible products. The definition above will be more convenient for us.
It is easy to see that Theorem 2.4 of [16] is equivalent to the theorem above with our definition. Still, we
give a self-contained proof.7
Proof. First we note that it is enough to prove the theorem for linear subspaces A and B of dimension
at least one: Given arbitrary sets A and B, let A0 , span(A) and B0 , span(B). If A and B both contain a
non-zero element (as required in the theorem), then A0 and B0 are linear subspaces of dimension at least
one. So we have that
dim(A0 · B0 ) ≥ min{n, dim(A0 ) + dim(B0 ) − 1} = min{n, dim(A) + dim(B) − 1} .
Now, we observe that span(A0 · B0 ) ⊆ span(A · B): An element of A0 · B0 has the form
(∑ ti · ai ) · (∑ s j · b j ) = ∑ ti · s j · ai · b j ,
i j i, j
where ai ∈ A, b j ∈ B and ti , s j ∈ Fq . This is obviously in span(A · B). So A0 · B0 ⊆ span(A · B), and this
implies span(A0 · B0 ) ⊆ span(A · B). Therefore, the equation above implies
dim(A · B) ≥ min{n, dim(A) + dim(B) − 1} .
We now turn to proving the theorem for linear subspaces A and B of dimension at least one. We proceed
by induction on dim(A). As a base, observe that the result holds trivially when dim(A) = 1. For the
inductive step, we may then assume that dim(A) > 1. We may also assume that B 6= Fqn as the theorem is
immediate in this case.
6 The theorem of [16] works also for non-prime n in which case the inequality involves the order of a certain subfield of F n .
q
7 Also, see Section 3.2 of [10] for a self-contained proof using the definition of [16].
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 674
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
Note that we may freely replace A by g · A (or B by g · B) for any g ∈ Fqn as this has no effect on
dim(A), dim(B), or dim(A · B). By this operation, we may assume that 1 ∈ A ∩ B. Since dim(A) > 1, we
may choose a ∈ A \ Fq . Let ` be the smallest nonnegative integer so that a` 6∈ B. Note that such ` exists
since Fqn = span(1, a, a2 , . . . , an−1 ) for any a ∈ Fqn \ Fq as there are no non-trivial subfields Fq ( K ( Fqn
when n is prime, and B 6= Fqn . Furthermore, ` > 0 by the assumption that 1 ∈ B. Next, replace B by
the set a−(`−1) · B. It now follows that 1 ∈ B and a 6∈ B, so A ∩ B is a proper nonempty subset of A. In
particular, 1 ≤ dim(A ∩ B) < dim(A).
Consider the Fq -linear subspaces A ∩ B and A + B and observe that (A ∩ B) · (A + B) ⊆ span(A · B).
The next equation follows from this and the induction hypothesis applied to A ∩ B and A + B.
dim(A · B) ≥ dim((A ∩ B) · (A + B))
≥ min{n, dim(A ∩ B) + dim(A + B) − 1}
= min{n, dim(A) + dim(B) − 1} .
This completes the proof.
3.3 Frobenius automorphisms of Fq
Let q = p` for prime p and let i ≥ 0 be an integer. Raising to power pi in Fq is known as a Frobenius
automorphism of Fq over F p and will play an important role. We record two useful and well-known
properties of this automorphism that will be used in our proofs.
i i i
• Linearity: ∀a, b ∈ Fq , (a + b) p = a p + b p .
i i
• Bijection: The map x → x p over Fq is bijective. In particular, for c ∈ Fq , c1/p is always (uniquely)
defined.
A useful fact following from these properties is that “taking the p-th power” of a set does not change
its dimension.
Claim 3.8 (Dimension preservation). Let q = p` from prime p and an integer `. For an integer i ≥ 1 and
i i i
a set A ⊆ Fqn let A p , {a p | a ∈ A}. Then dim(A) = dim(A p ).
Proof. Let {a1 , . . . , ak } ⊆ A be a basis for the Fq -span of A. Choose any c1 , . . . , ck ∈ Fq that are not all
zero. Then,
! pi
k k
i 1/pi
∑ c j · a pj = ∑ cj ·aj 6= 0 .
j=1 j=1
i i i
Thus {a1p , . . . , akp } are independent over Fq and therefore dim(A p ) ≥ dim(A). The reverse inequality is
similar.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 675
E LI B EN -S ASSON AND A RIEL G ABIZON
4 The main construction
As before, we use r to denote the number of inputs of f (Z1 , . . . , Zr ) ∈ M[n, k, d]. We denote by D the
product set {0, . . . , d}r . We use bold letters to denote vectors in Frq . For example, Z = (Z1 , . . . , Zr ). For
an element S = (s1 , . . . , sr ) ∈ D we use the notation
ZS , Z1s1 · · · Zrsr .
Fix f = ( f1 (Z), . . . , fn (Z)) ∈ M[n, k, d]. For 1 ≤ j ≤ n, we write
f j (Z) = ∑ a j,S · ZS .
S∈D
With the notation above, for S ∈ D let aS , (a1,S , . . . , an,S ) ∈ Fnq . Using the isomorphism of the vectors
spaces Fnq and Fqn , we can view aS as an element of Fqn and write
f (Z) = ∑ aS · ZS . (4.1)
S∈D
That is, we view f as a multivariate polynomial with coefficients in Fqn . A crucial observation is that
when f has large range the coefficients of f have large dimension.
Lemma 4.1 (Large range implies large span). Let f ∈ M[n, k, d]. As in (4.1), write f (Z) = ∑S∈D aS · ZS
where aS ∈ Fqn . Then dim{aS }S∈D\{0} ≥ k.
Proof. The range of f over inputs in Frq is contained in an affine shift of the Fq -linear span of {aS }S∈D\{0} .
Since this range is of size at least qk , we must have dim{aS }S∈D\{0} ≥ k.
A simple but crucial observation from [10] is that a polynomial with coefficients in Fqn whose non-
constant coefficients span Fqn over Fq can be “projected” to a non-constant polynomial with coefficients
in Fq . We formalize this in the definition and lemma below.
Definition 4.2 (Full-span polynomial). We say that a polynomial G ∈ Fqn [Z] = Fqn [Z1 , . . . , Zr ] has full
span if the coefficients of the non-constant monomials of G span Fqn over Fq .
Lemma 4.3 (Disperser for full-span polynomials). Suppose G ∈ Fqn [Z] has full span. Let T : Fqn → Fq be
a non-trivial Fq -linear mapping. Then T (G(Z)), as a function from Frq to Fq , agrees with a non-constant
polynomial in Fq [Z] whose total and individual degrees are at most those of G.
Proof. We write G(Z) = ∑S∈R aS · ZS for aS ∈ Fqn , where R ⊂ Nr denotes the set of tuples corresponding
to the monomials of G. For every x = (x1 , . . . , xr ) ∈ Frq , we have
!
T (G(x)) = T ∑ aS · xS = ∑ T (aS ) · xS ,
S∈R S∈R
where the last inequality used the Fq -linearity of T . Thus T (G(Z)) agrees on all inputs in Frq with the
polynomial F(Z) , ∑S∈R T (aS ) · ZS which is in Fq [Z]. The full span of G means that dim{aS }S∈R\{0} = n.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 676
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
Since T is a nontrivial linear map there is some S ∈ R such that T (aS ) 6= 0 and S 6= 0 and so F is a
non-constant polynomial. As the monomials with non-zero coefficients in F are a subset of the monomials
with non-zero coefficients in G, it is clear that the total and individual degrees of F are at most those of
G.
The previous lemma implies that to construct a disperser for polynomial sources it suffices to produce
a function that increases the span of low-degree polynomials. We do this in the next theorem which is of
paramount importance to this paper.
Theorem 4.4 (Product of distinct Frobenius automorphisms increases span). Fix a prime power q = p` .
Fix integers k ≤ n and d < s such that n is prime and s is a power of p. (In particular, raising to power
si is a Frobenius automorphism of Fq over F p .) Let u = d(n − k)/(k − 1)e. Then for any f (Z1 , . . . , Zr ) ∈
M[n, k, d], the polynomial
2 u u
f 1+s+s +···+s (Z1 , . . . , Zr ) = f (Z1 , . . . , Zr ) · f s (Z1 , . . . , Zr ) · · · f s (Z1 , . . . , Zr )
has full span.
Proof. Fix f ∈ M[n, k, d]. As in (4.1), write f (Z) = ∑S∈D aS · ZS with aS ∈ Fqn .
!1+s+s2 +···+su !si
u
1+s+s2 +···+su
f (Z) = ∑ aS · ZS =∏ ∑ aS · ZS .
S∈D i=0 S∈D
In what follows we use the notation Si = (Si,1 , . . . , Si,r ) and Si · si = (Si,1 · si , . . . , Si,r · si ). Using the linearity
of Frobenius automorphisms we continue the derivation and get
!
u u u
i i i i
=∏ ∑ asS · ZS·s = ∑ ∏ asS · ∏ ZS ·s i
i
i=0 S∈D S0 ,...,Su ∈D i=0 i=0
u u r
i Si, j ·si
= ∑ ∏ asS · ∏ ∏ Z j i
= ∑ AS0 ,...,Su · MS0 ,...,Su (Z) ,
S0 ,...,Su ∈D i=0 i=0 j=1 S0 ,...,Su ∈D
where
u u r
i S ·si
AS0 ,...,Su = ∏ asSi and MS0 ,...,Su (Z) = ∏ ∏ Z j i, j .
i=0 i=0 j=1
The crucial observation is that if (S0 , . . . , Su ) and (S00 , . . . , Su0 ) are two distinct tuples of elements of D
then the monomials MS0 ,...,Su (Z) and MS00 ,...,Su0 (Z) are distinct as well: Consider j ∈ {1, . . . , r} such that
Si, j 6= Si,0 j for some 0 ≤ i ≤ u. Then Z j is raised to power ∑ui=0 Si, j · si in MS0 ,...,Su (Z) and to power
∑ui=0 Si,0 j · si in MS00 ,...,Su0 (Z). These powers are different as for all 0 ≤ i ≤ u, Si, j , Si,0 j ≤ d < s, and there is
only one way to write an integer in base s with “coefficients” smaller than s. Define
A , {AS0 ,...,Su | S0 , . . . , Su ∈ D \ {0}} .
For 0 ≤ i ≤ u, define
i i
Bs , {asS | S ∈ D \ {0}} .
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 677
E LI B EN -S ASSON AND A RIEL G ABIZON
0 u i
Note that A = Bs · · · Bs . For all 0 ≤ i ≤ u, by Lemma 4.1 and Claim 3.8 we have dim(Bs ) ≥ k. Therefore,
by Theorem 3.6 we get
dim(A) ≥ min{n, k · (u + 1) − u} = n .
2 u
Our theorem follows by noticing that the coefficients of the non-constant monomials in f 1+s+s +···+s
u
contain the set A, hence f 1+s+···+s has full span.
Combining the lemma and theorem above we “project” into Fq and get a non-constant polynomial
with coefficients in Fq .
Theorem 4.5. Fix a prime power q = p` . Fix integers k ≤ n and d < s such that n is prime and s is a power
of p. Fix a non-trivial Fq -linear map T : Fqn → Fq . Let u = d(n − k)/(k − 1)e. Define P : Fqn → Fq by
2 u
P(x) , T (x1+s+s +···+s ). Fix any f (Z1 , . . . , Zr ) ∈ M[n, k, d] of total degree D. Then P( f (Z)), as a function
on Frq , agrees with a non-constant polynomial in Fq [Z] of total degree at most D · (1 + s + s2 + · · · + su ) <
D · su+1 and individual degree at most d · (1 + s + s2 + · · · + su ) = d · (su+1 − 1)/(s − 1).
Proof. Follows immediately from Lemma 4.3 and Theorem 4.4.
An immediate corollary is a construction of a “non-Boolean disperser” for polynomial sources.
Corollary 4.6. Fix a prime power q = p` . Fix integers k ≤ n and d < s such that n is prime and s is a power
of p. Fix a non-trivial Fq -linear map T : Fqn → Fq . Let u = d(n − k)/(k − 1)e. Define P : Fqn → Fq by
2 u
P(x) , T (x1+s+s +···+s ). Assume that q > d · (su+1 − 1)/(s − 1). Then, for any f (Z1 , . . . , Zr ) ∈ M[n, k, d]
we have that P( f (Z)) is a non-constant function from Frq into Fq .
Proof. Follows immediately from Theorem 4.5 by noticing that if P( f ) agrees with a non-constant
polynomial whose individual degrees are smaller than q, then it is a non-constant function from Frq into
Fq .
5 A useful criteria for the Weil bound
To get our main result we shall apply the Weil-Carlitz-Uchiyama bound for prefix projections (Corol-
lary 3.5) to a certain polynomial f ∈ Fq [Z], and so we have to ensure that f is not of the “degenerate”
form h p + h + c precluded by that bound. The common way to do this is to require gcd(deg( f ), p) = 1
(cf., [14, 10]). However we have less control over the degree of the polynomial f we need to work with.
For this reason, the following lemma will be very helpful to us. It gives us a simple way to “alter” f and
get a polynomial that is not of the form h p + h + c. The proof of the following lemma was shown to us by
Swastik Kopparty.
Lemma 5.1 (Criteria for non-degenerateness). Let q = p` for prime p and let v ≥ 2 be an integer such
that p - v. Let f ∈ Fq [Z] be a non-constant polynomial. If f is of the form gv for some g ∈ Fq [Z], it is not
of the form h p + h + c for any h ∈ Fq [Z] and c ∈ Fq .
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 678
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
Proof. Suppose by way of contradiction there exists f ∈ Fq [Z] of degree d ≥ 1 such that
f = gv = h p + h + c
for some g, h ∈ Fq [Z] and c ∈ Fq . Fix such an f with minimal degree d ≥ 1. It follows that deg(g) = d/v
and deg(h) = d/p. Taking a derivative in Fq [Z] of all 3 parts of the above equation we get
f 0 (Z) = v · gv−1 (Z) · g0 (Z) = h0 (Z) ,
where in the rightmost part we used the fact that the derivative of h p is zero. Notice that v 6= 0 in Fq
since p - v. If g0 6≡ 0 then this implies deg(h0 ) ≥ (v − 1) · deg(g) = d · (v − 1)/v. But deg(h0 ) < d/p ≤
d · (v − 1)/v. (For the last inequality we use p ≥ 2 and v ≥ 2.) So g0 and h0 are the zero polynomial. It is
not hard to see that this implies that all powers in g and h are multiples of p. So g = g1p and h = h1p for
some g1 , h1 ∈ Fq [Z]. We now have
f = (g1p )v = (h1p ) p + h1p + c .
This implies
gv1 = h1p + h1 + c1/p .
(Recall that a p-th root always exists in Fq .) Since gv1 has positive degree smaller than deg( f ) = d, this
contradicts the minimality of d and proves the lemma.
Reducing the multivariate case to the univariate case, we get the version of the Weil bound we need.
Lemma 5.2. Let q = p` for a prime p and integer ` > 0. Let f (Z1 , . . . , Zr ) ∈ Fq [Z1 , . . . , Zr ] be a non-
constant polynomial of total degree d < q. Assume that f = gv for an integer v ≥ 2 with p - v and
some g ∈ Fq [Z1 , . . . , Zr ]. Let m < ` be a positive integer. Then Em ( f (UFrq )) is ε-close to uniform for
ε = pm/2 · d · q−1/2 .
Proof. We note first that there must be an a = (a1 , . . . , ar ) ∈ Frq such that the univariate “line restriction”
polynomial
fa (Z) , f (a · Z) = f (a1 · Z, . . . , ar · Z)
has degree exactly d: The coefficient of Z d in fa is f d (a) where f d is the d-homogeneous part of f , i. e.,
the sum of monomials of degree exactly d in f . By the Schwartz-Zippel lemma as d < q, there is an
a ∈ Frq such that f d (a) 6= 0 and therefore fa (Z) has degree d. Fix such an a ∈ Frq . It follows that for all
b = (b1 , . . . , br ) ∈ Frq ,
fa,b (Z) , f (a · Z + b) = f (a1 · Z + b1 , . . . , ar · Z + br )
is non-constant, as the coefficient of Z d in fa,b is also f d (a). Furthermore, for any b ∈ Frq
fa,b = f (a1 · Z + b1 , . . . , ar · Z + br ) = gv (a1 · Z + b1 , . . . , ar · Z + br ) ,
and so fa,b is a v-th power of a polynomial in Fq [Z], and so by Lemma 5.1 is not of the form h p + h + c
for any h ∈ Fq [Z] and c ∈ Fq . As the distribution f (UFrq ) is a convex combination of the distributions
fa,b (UFq ) for the different “shifts” b ∈ Frq , the claim now follows from the Weil-Carlitz-Uchiyama bound
for prefix projections (Corollary 3.5).
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 679
E LI B EN -S ASSON AND A RIEL G ABIZON
6 A polynomial-source extractor
We can now state and prove our main technical theorem, which immediately implies our main theorem
on extractors for polynomial sources (Theorem 1.5).
Theorem 6.1 (Main–Extractors, parameterized version). Fix a field Fq of characteristic p, integers
1.2·n−k
d, D, 2 ≤ k ≤ n where n ≥ 25, and a positive integer m < 1/2 · log p q. Let α = 3D · (p · d) k−1 +2 . Assume
that q ≥ 2 · α 2 . There is an explicit (k, d, D, ε)-polynomial source extractor E : Fnq → Fmp with error
ε = pm/2 · α · q−1/2 .
Theorem 1.5 follows from the previous theorem by noticing that for 4 ≤ k ≤ n,
1.2 · n − k
+ 2 ≤ 3n/k .
k−1
Proof of Theorem 6.1. Choose a prime n ≤ n0 ≤ 1.2 · n (which always exists for n ≥ 25 according to
Nagura’s improvement of the Bertrand-Chebychev Theorem [19]). Given f (Z1 , . . . , Zr ) ∈ M[n, k, d] of
total degree D we think of f as an element of M[n0 , k, d] by padding its output with zeros. Let s be
0
the smallest power of p greater than d. Note that s ≤ p · d. Let P : Fnq → Fq be the polynomial in
Theorem 4.5 using s as above. If p = 2 let v = 3 and otherwise let v = 2. Let E : Fnq → Fmp be defined
as E(x) , Em (Pv (x)). From Theorem 4.5 we conclude that P( f (Z)) is non-constant of degree at most
D · su+1 where
1.2 · n − k
u = d(n0 − k)/(k − 1)e ≤ +1.
k−1
Hence, from Lemma 5.2 we see that Em (Pv ( f (UFrq ))) is ε-close to uniform for
1.2·n−k
ε = pm/2 · v · D · su+1 · q−1/2 ≤ pm/2 · 3D · (p · d) k−1 +2 · q−1/2 = pm/2 · α · q−1/2 .
Acknowledgements
We thank Swastik Kopparty for the proof of Lemma 5.1. We thank Swastik Kopparty and Shubhangi
Saraf for helpful discussions. We thank Zeev Dvir for reading a previous version of this paper. The first
author thanks Emanuele Viola for raising the question addressed in this paper. We thank the anonymous
referees for a careful reading and helpful comments.
References
[1] E LI B EN -S ASSON AND A RIEL G ABIZON: Extractors for polynomials sources over constant-size
fields of small characteristic. In Proc. 16th Internat. Workshop on Randomization and Computation
(RANDOM’12), pp. 399–410. Springer, 2012. [doi:10.1007/978-3-642-32512-0_34] 665
[2] E LI B EN -S ASSON , S HLOMO H OORY, E YAL ROZENMAN , S ALIL VADHAN , AND AVI W IGDER -
SON : Extractors for affine sources. Unpublished Manuscript, 2001. 668
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 680
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
[3] E LI B EN -S ASSON AND S WASTIK KOPPARTY: Affine dispersers from subspace polynomials. SIAM
J. Comput., 41(4):880–914, 2012. Preliminary version in STOC’09. [doi:10.1137/110826254] 668
[4] N ORBERT B LUM: A Boolean function requiring 3n network size. Theoret. Comput. Sci., 28(3):337–
345, 1983. [doi:10.1016/0304-3975(83)90029-4] 668
[5] J EAN B OURGAIN: On the construction of affine extractors. Geometric and Functional Analysis,
17(1):33–57, 2007. [doi:10.1007/s00039-007-0593-z] 668
[6] L EONARD C ARLITZ AND S ABURÔ U CHIYAMA: Bounds for exponential sums. Duke Math. J.,
24(1):37–41, 1957. [doi:10.1215/S0012-7094-57-02406-7] 673
[7] B ENNY C HOR AND O DED G OLDREICH: Unbiased bits from sources of weak randomness and
probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. Preliminary
version in FOCS’85. [doi:10.1137/0217015] 667
[8] A NINDYA D E AND T HOMAS WATSON: Extractors and lower bounds for locally samplable
sources. ACM Trans. Computation Theory, 4(1):3, 2012. Preliminary version in RANDOM’11.
[doi:10.1145/2141938.2141941] 668
[9] E VGENY D EMENKOV AND A LEXANDER S. K ULIKOV: An elementary proof of a 3n − o(n) lower
bound on the circuit complexity of affine dispersers. In 36th Internat. Symp. on Mathematical
Foundations of Computer Science (MFCS’11), pp. 256–265, 2011. [doi:10.1007/978-3-642-22993-
0_25] 668
[10] M ATT D E VOS AND A RIEL G ABIZON: Simple affine extractors using dimension expansion. In
Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 50–57. IEEE Comp. Soc. Press,
2010. [doi:10.1109/CCC.2010.14] 666, 668, 671, 674, 676, 678
[11] Z EEV DVIR: Extractors for varieties. Comput. Complexity, 21(4):515–572, 2012. Preliminary
version in CCC’09. [doi:10.1007/s00037-011-0023-3] 668
[12] Z EEV DVIR , A RIEL G ABIZON , AND AVI W IGDERSON: Extractors and rank extractors for
polynomial sources. Comput. Complexity, 18(1):1–58, 2009. Preliminary version in FOCS’07.
[doi:10.1007/s00037-009-0258-4] 668
[13] Z EEV DVIR AND S HACHAR L OVETT: Subspace evasive sets. In Proc. 44th STOC, pp. 351–358.
ACM Press, 2012. See also at ECCC. [doi:10.1145/2213977.2214010] 668
[14] A RIEL G ABIZON AND R AN R AZ: Deterministic extractors for affine sources over large fields.
Combinatorica, 28(4):415–440, 2008. Preliminary version in FOCS’05. [doi:10.1007/s00493-008-
2259-3] 668, 672, 673, 678
[15] V ENKATESAN G URUSWAMI: Linear-algebraic list decoding of folded Reed-Solomon codes. In
Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 77–85. IEEE Comp. Soc. Press,
2011. [doi:10.1109/CCC.2011.22] 668
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 681
E LI B EN -S ASSON AND A RIEL G ABIZON
[16] X IANG -D ONG H OU , K A H IN L EUNG , AND Q ING X IANG: A generalization of an addition theorem
of Kneser. J. Number Theory, 97(1):1–9, 2002. [doi:10.1006/jnth.2002.2793] 671, 672, 674
[17] X IN L I: A new approach to affine extractors and dispersers. In Proc. 26th IEEE Conf.
on Computational Complexity (CCC’11), pp. 137–147. IEEE Comp. Soc. Press, 2011.
[doi:10.1109/CCC.2011.27] 668
[18] RUDOLF L IDL AND H ARALD N IEDERREITER: Introduction to Finite Fields and Their Applications.
Cambridge Univ. Press, Cambridge, 1994. 672
[19] J ITSURO NAGURA: On the interval containing at least one prime number. Proc. Japan Acad.,
28(4):177–181, 1952. [doi:10.3792/pja/1195570997] 680
[20] A NUP R AO: An exposition of Bourgain’s 2-source extractor. Electron. Colloq. on Comput. Com-
plexity (ECCC), 14(034), 2007. ECCC. 673
[21] W OLFGANG M. S CHMIDT: Equations over Finite Fields: An Elementary Approach. Volume 536
of Lecture Notes in Mathematics. Springer, 1976. [doi:10.1007/BFb0080437] 673
[22] RONEN S HALTIEL: Dispersers for affine sources with sub-polynomial entropy. In Proc. 52nd
FOCS, pp. 247–256. IEEE Comp. Soc. Press, 2011. Full version available at author’s home page.
[doi:10.1109/FOCS.2011.37] 668
[23] E MANUELE V IOLA: Extractors for circuit sources. In Proc. 52nd FOCS, pp. 220–229. IEEE Comp.
Soc. Press, 2011. See also at ECCC. [doi:10.1109/FOCS.2011.20] 668
[24] J OHN VON N EUMANN: Various techniques used in connection with random digits. Applied Math
Series, 12:36–38, 1951. 666
[25] A NDRÉ W EIL: On some exponential sums. Proc. Nat. Acad. Sci. USA, 34(5):204–207, 1948. PNAS.
672
[26] A MIR Y EHUDAYOFF: Affine extractors over prime fields. Combinatorica, 31(2):245–256, 2011.
[doi:10.1007/s00493-011-2604-9] 668
[27] N OGA Z EWI AND E LI B EN -S ASSON: From affine to two-source extractors via approximate duality.
In Proc. 43rd STOC, pp. 177–186. ACM Press, 2011. [doi:10.1145/1993636.1993661] 668
AUTHORS
Eli Ben-Sasson
associate professor
Technion, Haifa, Israel
eli cs technion ac il
http://eli.net.technion.ac.il/
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 682
E XTRACTORS FOR P OLYNOMIAL S OURCES OVER F IELDS OF C ONSTANT O RDER
Ariel Gabizon
visiting researcher
Technion, Haifa, Israel
ariel gabizon gmail com
https://sites.google.com/site/arielgabizon1/
ABOUT THE AUTHORS
E LI B EN -S ASSON graduated from the Hebrew University in 2001. His advisor was Avi
Wigderson. He believes that the internet has killed the ritual of “telling a joke” (as
opposed to forwarding it). He is sometimes described as “relaxed” though feels stressed,
and enjoys the company of his wife and four kids.
A RIEL G ABIZON graduated from the Weizmann Institue in 2008. His advisors were Ran
Raz and Ronen Shaltiel. He is interested in using nice algebraic techniques for computer
science problems, and in figuring out how powerful the randomized complexity classes
are. He is a big supporter of practicing Vipassana meditation, and humanity gradually
becoming vegan. He loves anything to do with creativity and free expression, like theater
improv, singing, writing songs and dancing.
T HEORY OF C OMPUTING, Volume 9 (21), 2013, pp. 665–683 683