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