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 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 was used [E. Mossel, C. Umans, On the complexity of approximating the VC dimension, J. Comput. System Sci. 65 (2002) 660–671] to show that approximating VC dimension to within a factor of N1−δ is AM-hard for any positive δ.