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:00 PM - 3:00 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 notes 1 |
Wed. Aug 27 | Pairwise and k-wise independence | Lecture notes 2 |
Mon. Sep 1 | No class (Labor Day) | |
Wed. Sep 3 | k-wise independence (cont.), basic Boolean Fourier analysis | Lecture notes 3 |
Mon. Sep 8 | $\varepsilon$-biased distribution, almost k-wise independence | Lecture notes 4, Problem Set 1 (Due: Oct 6) |
Wed. Sep 10 | PRG for derandomization, BPL, branching programs | Lecture notes 5 |
Mon. Sep 15 | Nisan's generator | |
Wed. Sep 17 | Nisan's generator (cont.), BPL in SC | |
Mon. Sep 22 | Saks-Zhou theorem | |
Wed. Sep 24 | Expander graphs | |
Mon. Sep 29 | INW generator | |
Wed. Oct 1 | Randomness extractor | |
Mon. Oct 6 | Nisan-Zuckerman generator | Problem Set 2 (Due: Nov 3) |
Wed. Oct 8 | Hardness vs. randomness, Nisan-Wigderson generator | |
Mon. Oct 13 | No class (Fall Break) | |
Wed. Oct 15 | Trevisan's extractor | |
Mon. Oct 20 | Cryptographic PRG, PRF, PRP and one-way function | |
Wed. Oct 22 | Basics of quantum computing | |
Mon. Oct 27 | Learning with error, post-quantum PRG | |
Wed. Oct 29 | PRS and PRU, symmetric subspace, random phase states | Problem Set 3 (Due: Dec 1) |
Mon. Nov 3 | Unitary design, Clifford group, PFC constrcution | |
Wed. Nov 5 | (flexible) | |
Mon. Nov 10 | Student presentation | |
Wed. Nov 12 | Student presentation | |
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