A New Approach to Affine Extractors and Dispersers
We study the problem of constructing affine extractors over GF(2). Previously the only known con- struction 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 fraction of the entropy with exponentially small error. This matches the previous best result of Bourgain. The extractor can be pushed to handle affine sources with entropy n= p lognlogn. This slightly improves Bourgain's result and matches the recent result of Yehudayoff. We also give a zero-error disperser for affine sources with entropy n= p logn that outputs n (1) bits. This improves previous constructions 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 indepen- dent interest.