Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2005 | public
Journal Article

Simple extractors for all min-entropies and a new pseudorandom generator

Abstract

A "randomness extractor" is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure of the amount of randomness in a distribution.) We present a simple, self-contained extractor construction that produces good extractors for all min-entropies. Our construction is algebraic and builds on a new polynomial-based approach introduced by Ta-Shma et al. [2001b]. Using our improvements, we obtain, for example, an extractor with output length m = k/(log n)O(1/α) and seed length (1 + α)log n for an arbitrary 0 < α ≤ 1, where n is the input length, and k is the min-entropy of the input distribution. A "pseudorandom generator" is an algorithm that given a short random seed produces a long output that is computationally indistinguishable from uniform. Our technique also gives a new way to construct pseudorandom generators from functions that require large circuits. Our pseudorandom generator construction is not based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness directly into pseudorandomness. The parameters of our generator match those in Impagliazzo and Wigderson [1997] and Sudan et al. [2001] and in particular are strong enough to obtain a new proof that P = BPP if E requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal "hitting set generator" that stretches O(log n) random bits into sΩ(1) pseudorandom bits when given a function on log n bits that requires circuits of size s. This yields a quantitatively optimal hardness versus randomness tradeoff for both RP and BPP and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool nondeterministic circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for AM and the first hardness amplification result for nondeterministic circuits.

Additional Information

© 2005 ACM. RECEIVED OCTOBER 2002; REVISED MAY 2004; ACCEPTED NOVEMBER 2004. Some of the research of the first author was performed at the Institute for Advanced Study, Princeton, NJ, and at the Weizmann Institute of Research, Rehovot, Israel. During the second period, the first author was supported by the Koshland Scholarship. Some of the research of the second author was performed while he was a postdoc at Microsoft Research. He was also supported in part by NSF grant CCF-0346991.

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023