CSDM - Affine Dispersers from Subspace Polynomials

An affine disperser over F₂ⁿ for sources of dimension d is a function f: F₂ⁿ --> F₂ such that for any affine subspace S in F₂ⁿ of dimension at least d, we have {f(s) : s in S} = F₂ . 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)