Extractors from Reed-Muller Codes

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/.

Authors

• Amnon Ta-Shma
• David Zuckerman
• Muli Safra

Keywords

• Entropy
• Computer science
• Character generation
• Polynomials
• Error correction codes
• Virtual colonoscopy
• History
• Buildings
• Circuits
• Polynomial Of Degree
• Forward Error Correction
• Time And Space
• Polydispersity Index
• Binary Code
• Monomial
• Random Bits
• Query Point
• Weak Source
• Output Bits
• Polynomials In Variables