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

  1. Due : February 26, 2016.

Lecture Notes

  1. December 31, 2015. Introduction. Randomized Polynomial-Identity Testing
  2. January 1, 2016. Happy New Gregorian Calendar Year, randomized s-t connectivity
  3. January 11, 2016: Random walks, spectral gap and randomized s-t connectivity
  4. January 15, 2016: Mixing and Hitting times
  5. January 16, 2016: (contd.) and Basic Derandomization Techniques
  6. January 19, 2016. Basic derandomization - BPP vs. NP
  7. January 21, 2016. Basic derandomization - Pairwise independence
  8. January 25, 2016. Basic derandomization - error reduction and sampling
  9. January 28, 2016. Chernoff Bound
  10. January 29, 2016. Computational Indistinguishability.
  11. February 1, 2016. Pseudorandom sources from one-way permutations.
  12. February 4, 2016. Amplification of Linear Guesses
  13. February 5, 2016. Amplification of Linear Guesses. (contd.)
  14. February 8, 10, 12. Nisan-Wigderson Pseudorandom Generator
  15. February 15-21: Midsem week, no classes
  16. February 22, 25, 26. Reed Solomon Code, List decoding.
  17. February 29, March 3, 4. Reed Muller code, List decoding
  18. March 7. Impagliazzo-Wigderson Pseudorandom Generator.
  19. March 10. Extractors, Negative Results.
  20. March 11-18. Trevisan's Extractor.
  21. March 28. Expanders - Introduction
Tentative Schedule
  1. March 30. Eigenvalues and Expansion.
  2. March 31. Eigenvalues and Expansion.
  3. April 1. Expanders using the Zig-zag graph product.
  4. April 3. Expanders using the Zig-zag graph product.
  5. April 4 - 14. Monotone expanders and applications (tentative)