Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator

Abstract

We present a simple, self-contained extractor construction that produces good extractors for all min-entropies (min-entropy measures the amount of randomness contained in a weak random source). Our construction is algebraic and builds on a new polynomial-based approach introduced by A. Ta-Shma et al. (2001). Using our improvements, we obtain, for example, an extractor with output length m = k^(1-δ) and seed length O(log n). This matches the parameters of L. Trevisan's (1999) breakthrough result and additionally achieves those parameters for small min-entropies k. Our construction gives a much simpler and more direct solution to this problem. Applying similar ideas to the problem of building pseudo-random generators, we obtain a new pseudo-random generator construction that is not based on the NW generator (N. Nisan and A. Widgerson, 1994), and turns worst-case hardness directly into pseudo-randomness. The parameters of this generator are strong enough to obtain a new proof that P=BPP if E requires exponential size circuits. Essentially, the same construction yields a hitting set generator with optimal seed length that outputs s^(Ω(1)) bits when given a function that requires circuits of size s (for any s). This implies a hardness versus randomness trade off for RP and BPP that is optimal (up to polynomial factors), solving an open problem raised by R. Impagliazzo et al. (1999). Our generators can also be used to derandomize AM in a way that improves and extends the results of [4, 18, 20].