CS 744 : Pseudorandom Generators
Course Contents
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.
Course Requirements
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.)
Homeworks
- Due : February 26, 2016.
Lecture Notes
- December 31, 2015. Introduction. Randomized
Polynomial-Identity Testing
- 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
Derandomization Techniques
- January 19, 2016. Basic derandomization - BPP
vs. NP
- January 21, 2016. Basic derandomization -
Pairwise independence
- January 25, 2016. Basic derandomization - error
reduction and sampling
- January 28, 2016. Chernoff Bound
- January 29, 2016. Computational
Indistinguishability.
- February 1, 2016. Pseudorandom sources from
one-way permutations.
- February 4, 2016. Amplification of Linear
Guesses
- February 5, 2016. Amplification of Linear
Guesses. (contd.)
- February 8, 10, 12. Nisan-Wigderson Pseudorandom
Generator
- 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
Tentative Schedule
- 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
(tentative)