Seminar: May 26, 2009, 3:00pm

Eli Ben-Sasson, Technion

Affine Dispersers from Subspace Polynomials

Note non-standard day and time!

An affine disperser over a field F for sources of dimension d is a function f: F^n -> F that is nonconstant (i.e., takes more than one value) on inputs coming from a d-dimensional affine subspace of F^n.

Affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness, and in particular, generalize the notion of dispersers for bit-fixing sources. Previously, explicit constructions of affine dispersers were known for every d=\Omega(n), due to [Barak, Kindler, Shaltiel, Sudakov and Wigderson] and [Bourgain]. (The latter in fact gives stronger objects called affine extractors).

In this work we give the first explicit affine dispersers for sublinear dimension. Specifically, our dispersers work even when d> n^{4/5}. The main novelty in our construction lies in the method of proof, which relies on elementary properties of subspace polynomials. In contrast, the previous works mentioned above relied on sum-product theorems for finite fields.

Time permitting we shall discuss recent work which shows that some of our constructions are in fact affine extractors, i.e., the output of f is almost uniformly distributed on F.

Joint work with Swastik Kopparty.