David Zuckerman
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-561
February 1990
http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-561.pdf
We consider the following model for a weak random source: the source is asked only once for R bits, and the source outputs an R-bit string such that no string has probability more than 2^delta R of being output, for some fixed delta > 0. We show that under the Generalized Paley Graph Conjecture, there is a pseudo-random generator that simulates RP using as a seed a string from such a source for any delta > 0. For delta > 1/2, we can simplify our generator considerably and prove its correctness without relying on any unproven assumption. Cohen and Widgerson have also solved the case delta > 1/2 using different techniques. Finally, we prove that for any delta > 0 and for all but an exponential fraction of delta-sources, an even simpler generator can simulate RP.
BibTeX citation:
@techreport{Zuckerman:CSD-90-561, Author = {Zuckerman, David}, Title = {New Pseudo-Random Generators for Weak Random Sources}, Institution = {EECS Department, University of California, Berkeley}, Year = {1990}, Month = {Feb}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/6182.html}, Number = {UCB/CSD-90-561}, Abstract = {We consider the following model for a weak random source: the source is asked only once for <i>R</i> bits, and the source outputs an <i>R</i>-bit string such that no string has probability more than 2^delta<i>R</i> of being output, for some fixed delta > 0. We show that under the Generalized Paley Graph Conjecture, there is a pseudo-random generator that simulates RP using as a seed a string from such a source for any delta > 0. For delta > 1/2, we can simplify our generator considerably and prove its correctness without relying on any unproven assumption. Cohen and Widgerson have also solved the case delta > 1/2 using different techniques. Finally, we prove that for any delta > 0 and for all but an exponential fraction of delta-sources, an even simpler generator can simulate RP.} }
EndNote citation:
%0 Report %A Zuckerman, David %T New Pseudo-Random Generators for Weak Random Sources %I EECS Department, University of California, Berkeley %D 1990 %@ UCB/CSD-90-561 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/6182.html %F Zuckerman:CSD-90-561