Randomness is a powerful paradigm in computer science, and is often provides the simplest or most efficient algorithms for many computational problems. In fact, in some areas of computer science, such as cryptography, property testing and distributed algorithms, randomization is proven to be necessary to achieve certain tasks. It is therefore natural to conjecture (as many scientists initially did) that at least for some computational problems, randomization is inherently necessary: One cannot replace the probabilistic algorithm with a deterministic one without significant loss of efficiency. Surprisingly, recent research has provided more and more evidence that this is likely to be false.
The main paradigm used to derandomize probabilistic algorithms is that of pseudorandomness, the theory of efficiently generating objects that look random despite being constructed using little or no randomness.
The course will cover basic topics in derandomization and in pseudorandomness.
The following is a tentative list of topics that I will cover:
Randomized algorithms and basic derandomization techniques
Complexity classes that capture randomness
The Nisan-Wigderson Pseudorandom generator
Bounded independence
Randomness extractors
Nisan?s pseudorandom generator for space-bounded computation
Expander graphs