Affine dispersers from subspace polynomials

E Ben-Sasson, S Kopparty - Proceedings of the forty-first annual ACM …, 2009 - dl.acm.org
E Ben-Sasson, S Kopparty
Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009dl.acm.org
An affine disperser over F2n for sources of dimension d is a function f: F2n→ F2 such that for
any affine space S⊆ F2n of dimension at least d, we have {f (s): s in S}= F2. 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 …
An affine disperser over F2n for sources of dimension d is a function f: F2n → F2 such that for any affine space S ⊆ F2n of dimension at least d, we have {f(s) : s in S} = F2. 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 = Ω(n4/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.
ACM Digital Library