A New Approach to Affine Extractors and Dispersers
Xin Li · 2011
We study the problem of constructing affine extractors over GF(2). Previously the only known construction that can handle sources with arbitrarily linear entropy is due to Bourgain (and a slight modification by Yehudayoff), which makes extensive use of complicated inequality manipulations and relies on a careful choice of a polynomial. In this paper we give a new and conceptually much cleaner construction of affine extractors for linear entropy sources that outputs a constant fractionof the entropy with exponentially small error. This matches theprevious best result of Bourgain. The extractor can be pushed tohandle affine sources with entropy n/√(log n log n). This slightly improves Bourgain's result andmatches the recent result of Yehudayoff. We also give a zero-error disperser for affine sources with entropy n/√(log n) that outputs nΩ(1)bits. This improves previousconstructions of affine dispersers that output more than 1 bit. In contrast to Bourgain's construction, our construction mainly uses extractor machinery and basic properties of polynomials. Some of our techniques may be of independent interest.