A pseudorandom generator construction based on randomness extractors and combinatorial designs

Nisan and Wigderson in their seminal work introduced a new (conditional) pseudorandom generator construction which since then has been extensively used in con~plexity theory and has led to extensive further research. Impagliazzo and Wigderson (1997), and Sudan, Trevisan, and Vadhan (2001) have shown how this construction can be utilized to prove conditional derandomization results under weaker hardness assumptions. We study the construction of pseudorandom generators, and use an observation of Sudan et al. to recast the Impagliazzo-Wigderson construction in terms of weak sources of randomness; such a source is a distribution on binary strings that is \u27random\u27 in the sense of having high \u27entropy\u27. We will then use an efficient algorithm of Gabizon et al. to extract almost all of the randomness present, obtaining a pseudorandom generator that stretches O(n) bits to R(n2n) bits