CS59200 - PRS, Pseudorandomness (Fall 2025)

Course Information

Instructor: Wei Zhan weizhan [AT] purdue [dot] edu
Meetings: 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

Course Schedule

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