An affine disperser over F_{2}^{n} for sources of dimension d is a function f: F_{2}^{n} --> F_{2} such that for any affine subspace S in F_{2}^{n} of dimension at least d, we have {f(s) : s in S} = F_{2} . Affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness. Previously, explicit constructions of affine dispersers were known for every $d = O(n)$ , due to Barak-Kindler-Shaltiel-Sudakov-Wigderson and Bourgain (the latter in fact gives stronger objects called affine extractors).

In this talk, I will describe an explicit affine disperser for sublinear dimension. Specifically, the disperser works even when d = O(n^{4/5}) . The main novelty in our construction lies in the method of proof, which uses elementary properties of simple-but-powerful algebraic objects called subspace polynomials. In contrast, the previous works mentioned above relied on sum-product theorems for finite fields. (Joint work with Eli Ben-Sasson)

# CSDM - Affine Dispersers from Subspace Polynomials

Swastik Kopparty

Massachusetts Institute of Technology

September 15, 2009