An algebraic source is a random variable distributed
uniformly over the set of common zeros of one or more multivariate
polynomials defined over a finite field F. Our main result is
the construction of an explicit deterministic extractor for
algebraic sources over exponentially large prime fields. More
precisely, we give ... more >>>

We introduce the problem of constructing explicit variety evasive subspace families. Given a family \mathcal{F} of subvarieties of a projective or affine space, a collection \mathcal{H} of projective or affine k-subspaces is (\mathcal{F},\epsilon)-evasive if for every \mathcal{V}\in\mathcal{F}, all but at most \epsilon-fraction of W\in\mathcal{H} intersect every irreducible component of \mathcal{V} ... more >>>

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map f : \mathbb{F}_q^r \to \mathbb{F}_q^n to an element sampled uniformly at random from a k-dimensional variety V \subseteq \mathbb{F}_q^r. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>

We explicitly construct the first nontrivial extractors for degree d \ge 2 polynomial sources over \mathbb{F}_2^n. Our extractor requires min-entropy k\geq n - \frac{\sqrt{\log n}}{(d\log \log n)^{d/2}}. Previously, no constructions were known, even for min-entropy k\geq n-1. A key ingredient in our construction is an input reduction lemma, which allows ... more >>>