Skip to main content
Download PDF
- Main
Connections Between Randomness Extractors, Pseudorandom Generators, and Optimal Derandomization
- Lin, Dustin
- Advisor(s): Impagliazzo, Russell
Abstract
This thesis will be a survey aimed to be an overview of some connections betweenrandomness extractors and pseudorandom generators in complexity theory. Particularly there will be a focus on how such connections are leveraged in achieving faster derandomization and “beating the hybrid argument”. We will cover both some classic results and examples, as well as some more recent ones