ECCC-Report TR10-064https://eccc.weizmann.ac.il/report/2010/064Comments and Revisions published for TR10-064en-usTue, 13 Apr 2010 03:50:15 +0300
Paper TR10-064
| A New Approach to Affine Extractors and Dispersers |
Xin Li
https://eccc.weizmann.ac.il/report/2010/064We 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.Tue, 13 Apr 2010 03:50:15 +0300https://eccc.weizmann.ac.il/report/2010/064