CS59200 - PRS, Pseudorandomness (Fall 2025)
Course Information
Instructor: Wei Zhan weizhan [AT] purdue [dot] eduMeetings: Monday & Wednesday, 4:30 PM - 5:45 PM @ SCHM 226
Office hours: Monday 2:30 PM - 3:30 PM @ DSAI 1100
Credit hours: 3
CRN: 30227
Course Description
We all know that the random numbers generated from our computers are not truly random: they are generated deterministically from a short "seed", using certain clever algorithms which make them look random. What are the theoretical guarantees of these random numbers, and are they really necessary for algorithmic purposes?In this course we will learn about pseudorandomness, a theoretical abstraction of property that an object looks random to a specific class of distinguishers. We will meet a variety of pseudorandom objects, such as expander graphs, pseudorandom generators, and randomness extractors, and study their constructions and applications. We will also explore the pseudorandomness in the world of quantum computation, which was proposed in analogy to classical pseudorandomness but turns out to be surprisingly different.
Grading
- Homework (3 assignments): 10% each, 30% total;
- Each assignment will contain two problems, approximately due in one month after release (see the schedule below). The submissions must be in PDF format.
- You are encouraged to discuss with others, including me during my office hours, but only after making substantial effort on the problems by yourself. The solutions must be written individually, and any significant outside contribution should be properly acknowledged.
- The solutions should be written in formal mathematical language. There will be no partial credits for false proofs.
- Scribing: 10%;
- Each student will scribe for two lectures of their choice in LaTeX (template), submitted within one week after the lectures.
- You can volunteer for more, but they are not for credit. I will also release my notes for each week to help you digest the content.
- Presentation: 60%.
- At the end of the semester, each student will give an one-hour presentation for one paper with topic closely related to this course.
- You should send me the paper title and link and your desired presentation date for approval, no later than the last normal lecture. The availablities of the papers and dates are on a first-come-first-served basis.
- The presentation will be graded based on demonstration of a high-level understanding of the topic and the clarity in delivery. So reading other related papers and surveys will also be helpful, and try to focus on making other students understand as much as possible in your presentation (in other words, your target audience should not be me).
Course Schedule
Note that the schedule below will be updated along the course progression.| Date | Topic | Note |
|---|---|---|
| Mon. Aug 25 | Course overview, definition of pseudorandomness | Lecture 1 notes |
| Wed. Aug 27 | Pairwise and k-wise independence | Lecture 2 notes |
| Mon. Sep 1 | No class (Labor Day) | |
| Wed. Sep 3 | k-wise independence (cont.), basic Boolean Fourier analysis | Lecture 3 notes |
| Mon. Sep 8 | $\varepsilon$-biased distribution, almost k-wise independence | Lecture 4 notes, Problem Set 1 (Due: Oct 6) |
| Wed. Sep 10 | PRG for derandomization, BPL, branching programs | Lecture 5 notes |
| Mon. Sep 15 | Nisan's generator | |
| Wed. Sep 17 | Nisan's generator (cont.), BPL in SC | Lecture 6,7 notes |
| Mon. Sep 22 | Saks-Zhou theorem | Lecture 8 notes |
| Wed. Sep 24 | INW generator, expander graphs | Lecture 9 notes |
| Mon. Sep 29 | Spectral expansion | Lecture 10 notes |
| Wed. Oct 1 | Graph products, constructions of expanders | Lecture 11 notes |
| Mon. Oct 6 | Randomness extractor | Lecture 12 notes, Problem Set 2 (Due: Nov 3) |
| Wed. Oct 8 | Nisan-Zuckerman generator | Lecture 13 notes |
| Mon. Oct 13 | No class (Fall Break) | |
| Wed. Oct 15 | Hardness vs. randomness, Nisan-Wigderson generator | Lecture 14 notes |
| Mon. Oct 20 | Impagliazzo-Wigderson generator, Trevisan's extractor | Lecture 15 notes |
| Wed. Oct 22 | Cryptographic PRG and one-way functions | Lecture 16 notes |
| Mon. Oct 27 | Basics of quantum computing | Lecture 17 notes |
| Wed. Oct 29 | Post-quantum PRG, learning with error | Lecture 18 notes |
| Mon. Nov 3 | Basics of quantum computing (cont.), Haar measure | Lecture 19 notes, Problem Set 3 (Due: Dec 1) |
| Wed. Nov 5 | Pseudorandom states, state design | Lecture 20 notes |
| Mon. Nov 10 | Symmetric subspace, random phased state | Lecture 21 notes |
| Wed. Nov 12 | Pseudorandom unitaries, unitary design, Clifford group | Lecture 22 notes |
| Mon. Nov 17 | Student presentation | |
| Wed. Nov 19 | Student presentation | |
| Mon. Nov 24 | Student presentation | |
| Wed. Nov 26 | No class (Thanksgiving Break) | |
| Mon. Dec 1 | Student presentation | |
| Wed. Dec 3 | Student presentation | |
| Mon. Dec 8 | Student presentation | |
| Wed. Dec 10 | Student presentation |
Resources
There is no required textbook. For for classical pseudorandomness, the standard material is:- Pseudorandomness by Salil Vadhan
- Theory of Unconditional Pseudorandom Generators by Pooya Hatami and William Hoza
- Pairwise Independence and Derandomization by Michael Luby and Avi Wigderson
- Expander Graphs and Their Applications by Shlomo Hoory, Nathan Linial and Avi Wigderson
- Pseudorandomness and Combinatorial Constructions by David Zuckerman
- Pseudorandomness and Combinatorial Constructions by Luca Trevisan
- Pseudorandomness and Combinatorial Constructions by Eshan Chattopadhyay
- Pseudorandomness by Avishay Tal
- Derandomizing Space-Bounded Computation by William Hoza
- How to Construct Quantum Random Functions by Mark Zhandry
- Pseudorandom Quantum States by Zhengfeng Ji, Yi-Kai Liu, and Fang Song
- Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial by Antonio Anna Mele