Thumbnail
Access Restriction
Open

Author Trevisan, Luca
Source CiteSeerX
Content type Text
Publisher ACM Press
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Several Application ♦ New Approach ♦ Weakly Random Distribution ♦ Nisan-wigderson Pseudorandom Generator ♦ Pseudo-random Generator ♦ Previous Construction ♦ Standard Technique ♦ Known Result ♦ Near-optimal Extractor ♦ Explicit Construction ♦ Extractor Combinatorial Object ♦ Straightforward Application ♦ Certain Parameter ♦ Introduction Informally ♦ Related Result
Description We introduce a new approach to construct extractors --- combinatorial objects akin to expander graphs that have several applications. Our approach is based on error correcting codes and on the Nisan-Wigderson pseudorandom generator. A straightforward application of our approach yields a construction that is simple to describe and analyze, does not use any of the standard techniques used in related results, and improves or subsumes almost all the previous constructions. 1 Introduction Informally defined, an extractor is a function that extracts randomness from a weakly random distribution. Explicit constructions of extractors have several applications and are typically very hard to achieve. In this paper we introduce a new approach to the explicit construction of extractors. Our approach yields a construction that improves most of the known results, and that is optimal for certain parameters. Furthermore, our construction is simple and uses techniques that were never used in this field...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1998-01-01
Publisher Institution Electronic Colloquium on Computational Complexity