CS59200 - PRS, Pseudorandomness (Fall 2025)
Course Information
Instructor: Wei ZhanMeetings: Monday & Wednesday, 4:30 PM - 5:45 PM @ SCHM 226
Office hours: Friday 2:00 PM - 3:00 PM
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 post my notes after each lecture 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, k-wise independence | |
Wed. Aug 27 | almost k-wise independence, $\varepsilon$-biased distribution, basic Boolean Fourier analysis | |
Mon. Sep 1 | No class (Labor Day) | |
Wed. Sep 3 | PRG and PRF, derandomization, branching programs, logspace computation | |
Mon. Sep 8 | Expander graphs | Problem Set 1 (Due: Oct 6) |
Wed. Sep 10 | INW generator | |
Mon. Sep 15 | Reingold's theorem | |
Wed. Sep 17 | Randomness extractor | |
Mon. Sep 22 | Nisan-Zuckerman generator | |
Wed. Sep 24 | Nisan's generator, BPL in SC | |
Mon. Sep 29 | Saks-Zhou theorem | |
Wed. Oct 1 | Error-correcting codes, list-decoding | |
Mon. Oct 6 | Hardness vs. randomness, Nisan-Wigderson generator, Trevisan's extractor | Problem Set 2 (Due: Nov 5) |
Wed. Oct 8 | No class (Fall Break) | |
Mon. Oct 13 | Worst-case to average case reduction, Yao's XOR Lemma | |
Wed. Oct 15 | Goldreich-Levin theorem, Impagliazzo-Wigderson generator | |
Mon. Oct 20 | Basics of quantum computing | |
Wed. Oct 22 | Learning with error, post-quantum OWF, PRF and PRP | |
Mon. Oct 27 | Haar measure, PRS and PRU, comparison with classical pseudorandomness | |
Wed. Oct 29 | State design, symmetric subspace, random phase states | |
Mon. Nov 3 | Oracle separation between PRS and OWF | |
Wed. Nov 5 | Unitary design, Clifford group | Problem Set 3 (Due: Dec 3) |
Mon. Nov 10 | PFC construction, path recording technique | |
Wed. Nov 12 | (Flexible) | |
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
- 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