Hardcore measures, dense models and low complexity approximations

Continuing the study of connections amongst Dense Model Theorem, Low Complexity Approximation Theorem and Hardcore Lemma initiated by Trevisan et al. [TTV09], this thesis builds on the work of Barak et al., Impagliazzo, Reingold et al. and Zhang [BHK09, Imp09, RTTV08a, Zha11] to show the essential equivalence of these three results. The first main result obtained here is a reduction from any of the standard black-box Dense Models Theorems to the Low Complexity Approximation Theorem. The next is the extension of Impagliazzo's reduction from Strong Hardcore Lemma to Dense Model Theorem. Then using Zhang's Dense Model Theorem algorithm we reduce Weak Hardcore Lemma to Strong Hardcore Lemma. Last we distill the methods of Barak et al. and Zhang to extract a single algorithm which yields uniform constructions for all three. Putting all this together demonstrates the three results are essentially equivalent.