Abstract:

A fundamental question of Complexity Theory concerns the power of
probabilistic algorithms. It is conjectured that every poly-time
probabilistic algorithm can be derandomized into a poly-time
deterministic algorithm. (A recent example is the deterministic
poly-time algorithm for primality testing of Agarwal et al.)
  
The hardness versus randomness paradigm attempts to derandomize
all probabilistic algorithms by using unproven assumptions that
resemble The P versus NP assumption. Such results show that if
certain hard functions exist then there exist "pseudo-random
generators" which deterministically and efficiently generate long
sequences of "pseudo-random" bits. These sequences have the
property that no efficient algorithm can distinguish them from
truly random bits. It follows that we can derandomize any
efficient probabilistic algorithm by running it with
"pseudo-random" bits instead of truly random bits.
   
In the talk I will survey the hardness versus randomness paradigm
and present a new construction of pseudo-random generators. This
construction (which is joint work with Chris Umans) improves and
simplifies previous results in this area.