Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-036 | 2nd May 2001 00:00

Extractors from Reed-Muller Codes


Authors: Amnon Ta-Shma, David Zuckerman, Shmuel Safra
Publication: 2nd May 2001 21:28
Downloads: 1149


Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, researchers had failed to build extractors directly from a good code, without using other tools from pseudorandomness. We succeed in constructing an extractor directly from a Reed-Muller code. To do this, we develop a novel proof technique.

Furthermore, our construction is the first and only construction with degree close to linear.
In contrast, the best previous constructions had brought the log of the degree within a constant of optimal, which gives polynomial degree. This improvement is important for certain applications. For example, it follows that approximating the VC dimension to within
a factor of $N^{1-\delta}$ is AM-hard for any positive $\delta$.

ISSN 1433-8092 | Imprint