David Zuckerman

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-90-561

1990

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^deltaR 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},
    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