Academic
Publications
A New Approach to Affine Extractors and Dispersers

A New Approach to Affine Extractors and Dispersers,10.1109/CCC.2011.27,Xin Li

A New Approach to Affine Extractors and Dispersers   (Citations: 3)
BibTex | RIS | RefWorks Download
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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Currently the best explicit extractor for an (n;k) affine source only achieves entropy k = n= p log logn [4], [5]...
    • ...To our best knowledge there has been no result on this problem before, although a result in [5] implies such an extractor with k = n for any constant 0 < < 1. In this paper we also improve this result...
    • ...The process of converting X to X is conceptually similar to what we did in the three source extractor case, except here we use techniques about affine sources developed in [6], [5]...

    Xin Li. Improved Constructions of Three Source Extractors

    • ...Most of the research on explicit constructions focuses on the case q =2[ BKS + 10, Bou07, Rao09b, BSK09, Yeh10, Li11b, Sha11]...
    • ...The latter show existence of extractors for affine sources with min-entropy at least k = O(log n). The best known explicit extractor is due to Bourgain [Bou07] and works for affine sources with min-entropy at least k = o(n) (slight improvements to k = n/ √ log log n were given in [Yeh10, Li11b])...
    • ...– Construct affine extractors for the field F2 with min-entropy k< √ n .T he best known construction achieves k = n/ √ log log n [Bou07, Yeh10, Li11b]...

    Ronen Shaltiel. An Introduction to Randomness Extractors

Sort by: