Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

摘要

We introduce a new approach to construct extractors -- combinatorial objects akin to expander graphs that have several applications. Our approach is based on error correcting codes and on the Nisan-Wigderson pseudorandom generator. An application of our approach yields a construction that is simple to describe and analyze, does not utilize any of the standard techniques used in related results, and improves or subsumes almost all the previous constructions.