affine dispersers from subspace polynomials
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 space S ? 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 = ?(n), due to Barak et. al.[2] and Bourgain[10] (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.
randomness extractors