**Instructor**: Eshan Chattopadhyay

**Class schedule:** Tuesdays and Thursdays, 10:10-11:25am

**Location:** Hollister Hall 368

**Office hours**: Thursdays, 3-4pm (Gates 319), or by appointment

Piazza: Announcements and discussion

CMS: HW posting and submission

** Tentative list of topics**

- Basic introduction to pseudorandomness and derandomization. Will include introduction to simple pseudorandom distributions, hash functions, some properties of polynomials over finite fields, error correcting codes, and expander graphs.
- Producing random bits from defective sources and applications. This topic will be studied in depth. The key notion is that of a Randomness Extractor. We will study seeded extractors, non-malleable extractors, extractors for independent sources. We will see applications to combinatorics (to objects known as Ramsey graphs) and to cryptography.
- Derandomization in the space-bounded setting: A basic question in computational complexity theory is whether using random bits can save the amount of space used by algorithms. We will study this in detail.

- Scribe notes: 30%. You are expected to scribe at least 2 lectures (this might change depending on enrollment). You will be required to send in the scribed notes by 48 hours after the lecture.
- Homeworks: 20%. There will be 2 homework assignments well spread in the semester. Solving problems will require original thinking, and it will be a good idea to start early. You will be required to use LaTeX to typeset your solutions.
- Project: 40%. You are expected to pick a topic and send a project proposal by October 28. You may work in groups (up to 2 members).
- Participation: 10%. You are expected to show up to class and participate in discussions.

- Lecture 1: Introduction. pdf
- Lecture 2: Pairwise Independence. pdf
- Leture 3: k-wise independence, Probabilistic method. pdf
- Lecture 4: Expander graphs pdf
- Lecture 5: Expander Mixing Lemma, vertex expansion from spectral expansion pdf
- Lecture 6: Randon walks on Expanders I: Hitting property pdf
- Lecture 7: Random walks on Expanders II: chernoff bound pdf
- Lecture 8: Graph products pdf
- Lecture 9: Zig-zag product and construction of explicit expanders pdf
- Lecture 10: Introduction to randomness extraction
- Lecture 11: Seeded extractors, hash functions pdf
- Lecture 12: Leftover hash lemma, extractors from expanders pdf
- Lecture 13: Introduction to error-correcting codes pdf (lecturer: Jesse Goodman)
- Lecture 14: Gilbert-Varshamov bound pdf
- Lecture 15: Unique decoding Reed-Solomon codes, Johnson bound for list-decoding radius pdf
- Lecture 16: List decoding Reed-Solomon codes, Seeded extractor from codes pdf
- Lecture 17: List view of expanders, graph view of list-decodable codes pdf
- Lecture 18: Lossless vertex expanders from PV codes pdf
- Lecture 19: The Hadamard two-source extractor
- Lecture 20: 2-source extractors from Paley graphs
- Lecture 21: Small-biased spaces: constructions and connections
- Lecture 22: Space bounded derandomization: Nisan's generator pdf

- Pseudorandomness by Salil Vadhan
- Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan is a great source for the prerequisite probability theory background for this course.
- Expander graphs by Shlomo Hoory, Nati Linial, and Avi Wigderson.