Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-064 | 13th April 2010 01:51

A New Approach to Affine Extractors and Dispersers


Authors: Xin Li
Publication: 13th April 2010 03:50
Downloads: 2428


We study the problem of constructing affine extractors over $\mathsf{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 relies heavily on the technique of Van der Corput differencing and a careful choice of a polynomial.

In this paper we give a new and arguably simpler 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/\sqrt{\log n \log
n}$. 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/\sqrt {\log n}$
that outputs $n^{\Omega(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.

ISSN 1433-8092 | Imprint