|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 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. REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
INDEX TERMS
Primary Classification:
Additional Classification:
Keywords:
REVIEW
"Bruce E. Litow : Reviewer"
This paper continues an investigation into constructions of extractors and pseudorandom number generators (PNGs). The authors present a simple
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage Privacy Policy Code of Ethics Contact Us Useful downloads:  Adobe Acrobat
 QuickTime
 Windows Media Player
 Real Player
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Pdf
F.0