The Taub Faculty of Computer Science Events and Talks

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.

Joint work with Swastik Kopparty.