I will survey the ideas that led to this understanding, and in particular the main concept of a pseudo-random generator. Two fundamentally different constructions of such generators are known:
1) Generators based on one-way functions, yielding theorems like:
Theorem 1: If FACTORING has no subexponential size Boolean circuits, then BPP=P (eg randomness is useless in efficient computation!).
2) Generators based on arbitrary hard functions in EXP, yielding e.g.
Theorem 2: If PERMANENT has no subexponential size circuits, then BPP=P.
I will describe the costructions of both types of generators, the relative merits of both types, other applications and open problems.
Host: Andrew Yao