Extractors from Reed-Muller codes
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 638-647
- https://doi.org/10.1109/sfcs.2001.959940
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 N/sup 1-/spl delta// is AM-hard for any positive /spl delta/.Keywords
This publication has 26 references indexed in Scilit:
- Expanders That Beat the Eigenvalue Bound: Explicit Construction and ApplicationsCombinatorica, 1999
- Computing with Very Weak Random SourcesSIAM Journal on Computing, 1999
- Decoding of Reed Solomon Codes beyond the Error-Correction BoundJournal of Complexity, 1997
- Simulating BPP using a general weak random sourceAlgorithmica, 1996
- Randomness is Linear in SpaceJournal of Computer and System Sciences, 1996
- Hardness vs randomnessJournal of Computer and System Sciences, 1994
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- Expanders, randomness, or time versus spaceJournal of Computer and System Sciences, 1988
- On using deterministic functions to reduce randomness in probabilistic algorithmsInformation and Computation, 1987
- Generating quasi-random sequences from semi-random sourcesJournal of Computer and System Sciences, 1986