Resource type
Thesis type
(Thesis) M.Sc.
Date created
2006
Authors/Contributors
Author: Mahabadi, Ladan A.
Abstract
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 'random' in the sense of having high 'entropy'. 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.
Document
Copyright statement
Copyright is held by the author.
Scholarly level
Language
English
Member of collection
Download file | Size |
---|---|
etd2225.pdf | 973.19 KB |