View Related Documents

Abstract

We survey recent works which unify four of the most important and widely studied objects in the theory of pseudorandomness, namely: pseudorandom generators, expander graphs, error-correcting codes, and extractors. Since all of these objects are “pseudorandom” in some sense, it is not surprising that constructions of one of these objects may be useful in constructing another. Indeed, there are many examples of this in the past, which we do not attempt to summarize here. Instead, we focus on how recent works show that some of these objects are almost the same, when interpreted appropriately. All of the connections we describe involve extractors, lending further credence to Nisan’ assertion that they “exhibit some of the most ‘random-like’ properties of explicitly constructed combinatorial structures” [Nis96].

Fulltext Preview

Image of the first page of the fulltext document