Name
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 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 - \delta is AM-hard for any positive \delta. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.jcss.2005.05.010 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
polynomial degree,certain application,reed–muller codes,pseudorandomness,good code,previous construction,reed-muller codes,approximating vc dimension,reed-muller code,expanders,important derandomization goal,derandomization,inapproximability,extractors,good error,degree close,previous research,vc dimension,computational complexity,reed muller codes,random processes,theorem proving | Journal | 72 |
Issue | ISSN | ISBN |
5 | Journal of Computer and System Sciences | 0-7695-1390-5 |
Citations | PageRank | References |
48 | 2.25 | 36 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| amnon tashma a | 1 | 48 | 2.25 |
| David Zucherman | 2 | 2588 | 266.65 |
| Shmuel Safra | 3 | 2885 | 259.32 |