A pseudorandom generator construction based on randomness extractors and combinatorial designs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2006
Authors/Contributors
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.
Permissions
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact summit-permissions@sfu.ca.
Scholarly level
Language
English
Member of collection
Attachment Size
etd2225.pdf 973.19 KB