Computational pseudo-randomness

Summary form only given, largely as follows. One of the most important and fundamental discoveries of Theoretical Computer Science is the surprising connection between the computational power of randomness, and computational lower bounds on explicit functions. The currently strongest result of this form states: If EXP has no subexponentially small circuits then BPP had deterministic, pseudo-polynomial time algorithms. The key mechanism behind this connection is called a pseudo-random generator. There are two different constructions known - the “classical” one, which uses the difficulty of computing functions whose inverse is easy, and the more recent one which can use essentially any hard function. The talk will motivate and define the notions above. Then it will survey the main ideas behind the constructions of both generators, the proofs that they are pseudo-random, and the theorem above