CS59200 - PRS, Pseudorandomness (Fall 2025)

Course Information

Instructor: Wei Zhan
Meetings: 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

Course Schedule

Note that the schedule below will be updated along the course progression.
DateTopicNote
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: Some of the previously-taught courses on classical pseudorandomness: I am not aware of a standard material for quantum pseudorandomness. Some of introductory or foundational papers to the topic: