Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1059513.1059516 | IEEE Symposium on Foundations of Computer Science |
Keywords | Field | DocType |
randomness tradeoff,hardness versus randomness,log n bit,simple extractor,Nisan-Wigderson generator,randomness extractor,new pseudorandom generator,pseudorandom generator construction,short random seed,pseudorandom bit,pseudorandom generator,self-contained extractor construction,log n,hardness amplification result | Discrete mathematics,Randomness extractor,Computer science,Random seed,Pseudorandom generator | Journal |
Volume | Issue | ISSN |
52 | 2 | 0004-5411 |
ISBN | Citations | PageRank |
0-7695-1116-3 | 94 | 3.51 |
References | Authors | |
50 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ronen Shaltiel | 1 | 953 | 51.62 |
| Christopher Umans | 2 | 879 | 55.36 |