General Pseudo-random Generators from Weaker Models of Computation

摘要

The construction of pseudo-random generators (PRGs) has been based on strong assumptions like the existence of one-way functions or exponential lower bounds for the circuit complexity of Boolean functions. Given our current lack of satisfactory progress towards proving these assumptions, we study the implications of constructing PRGs for weaker models of computation to the derandomization of general classes like BPP. More specifically, we show how PRGs that fool monotone circuits could lead to derandomization for general complexity classes, and how the Nisan-Wigderson construction could use hardness results for monotone circuits to produce pseudo-random strings.