Title :
Extractors from Reed-Muller codes
Author :
Ta-Shma, Amnon ; Zuckerman, David ; Safra, Shmuel
Author_Institution :
Dept. of Comput. Sci., Tel Aviv Univ., Israel
Abstract :
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous 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 to achieve a degree close to linear. In contrast, the best previous constructions 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 N1-δ is AM-hard for any positive δ.
Keywords :
Reed-Muller codes; computational complexity; error correction codes; random processes; theorem proving; AM-hard; Reed-Muller code extractors; VC dimension; derandomization goal; error correcting codes; explicit extractors; polynomial degree; proof technique; pseudorandom generators; pseudorandomness; Buildings; Character generation; Circuits; Computer science; Entropy; Error correction codes; History; Polynomials; Virtual colonoscopy;
Conference_Titel :
Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on
Print_ISBN :
0-7695-1116-3
DOI :
10.1109/SFCS.2001.959940