An outline of the course can be found here. We plan to cover some basic derandomization techniques, and then proceed to a discussion of the Nisan-Wigderson and the Impagliazzo-Wigderson pseudorandom generators. We will also discuss the related notion of extractors, and discuss expander graphs. According to the remaining time available, we will try to cover the new results in meta-complexity, relating one-way functions to average case complexity, circuit minimization and time-bounded Kolmogorov complexity.
The course will be graded on 2 assignments, a midsemester exam and an end-semester exam. The assignments will constitute 40 percentage of the course score, the midsem, and the endsem, the remaining 30 percent each.
Solutions to the assignments have to be typed and submitted in soft-copy form to the Teaching Assistant. You can choose your favourite software, but we recommend TeX/LaTeX. Please do not hand in handwritten submissions or send their scanned versions. (Documents composed in LaTeX do tend to have shorter proofs, perhaps because editing and rewriting is easier.)