# 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. 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.

## Course Requirements

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.)

## Homeworks

HW2

## Lecture Notes

- August 1-2, 2023. Introduction. Randomized
Polynomial-Identity Testing
- Yao's XOR lemma(to be updated)
- Impagliazzo
"Hardcore" Lemma(updated on Thursday, August 17,
2023.)
- Error-Correcting Codes:Encoding
(Handwritten notes)
- Pseudorandom generators(Oct 3)
- Expanders and
Extractors(Oct 17: ongoing)