CS 744 : Pseudorandom Generators
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 to the level of detail that the
remaining time permits.
The course will be graded on 2-3 assignments, a midsemester exam
and an end-semester exam. The assignments will constitute 30
percentage of the course score, the midsem, 30 percent, and the
endsem, the remaining 40 percent.
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.)
- Due : February 26, 2016.
- December 31, 2015. Introduction. Randomized
- January 1, 2016. Happy New Gregorian Calendar Year, randomized s-t connectivity
- January 11, 2016: Random walks, spectral gap and
randomized s-t connectivity
- January 15, 2016: Mixing and Hitting times
- January 16, 2016: (contd.) and Basic
- January 19, 2016. Basic derandomization - BPP
- January 21, 2016. Basic derandomization -
- January 25, 2016. Basic derandomization - error
reduction and sampling
- January 28, 2016. Chernoff Bound
- January 29, 2016. Computational
- February 1, 2016. Pseudorandom sources from
- February 4, 2016. Amplification of Linear
- February 5, 2016. Amplification of Linear
- February 8, 10, 12. Nisan-Wigderson Pseudorandom
- February 15-21: Midsem week, no classes
- February 22, 25, 26. Reed Solomon Code, List decoding.
- February 29, March 3, 4. Reed Muller code, List decoding
- March 7. Impagliazzo-Wigderson Pseudorandom Generator.
- March 10. Extractors, Negative Results.
- March 11-18. Trevisan's Extractor.
- March 28. Expanders - Introduction
- March 30. Eigenvalues and Expansion.
- March 31. Eigenvalues and Expansion.
- April 1. Expanders using the Zig-zag graph product.
- April 3. Expanders using the Zig-zag graph product.
- April 4 - 14. Monotone expanders and applications