CMSC 39600-1: Pseudorandomness (Autumn 2023)

Full Course Title: "Topics in Theoretical Computer Science: Pseudorandomness"

Term: Autumn 2023 at the University of Chicago

Instructor: William Hoza (

Meetings: Tuesdays and Thursdays, 9:30am - 10:50am, JCL 354

Office Hours: Tuesdays, 11am - 12pm, JCL 311

Jump to: (loading...)

    Course Description What is the role of randomness in computing? Algorithm designers often introduce random choices into their algorithms in an effort to solve problems as efficiently as possible. This is a powerful and valuable paradigm, but it raises the question, where are we supposed to get random bits so that we can run these algorithms? In this course, we will think of randomness as an "expensive" or "scarce" computational resource. All else being equal, an algorithm that uses fewer random bits is better than an algorithm that uses more random bits, just like a faster algorithm is better than a slower algorithm. With this motivation, we will study pseudorandomness, i.e., we will study objects that appear more random than they actually are. We will mainly focus on the theory of unconditional pseudorandom generators, which use a small truly random "seed" to generate a long sequence of bits that appear random to any "sufficiently efficient" observer. Other topics will include randomness extractors, the derandomization of algorithms, and expander graphs.

    Course Timeline (The information below will be updated throughout the quarter.)

    Part I: Small-Bias Distributions and Limited Independence. Tentative topic list: defining pseudorandom generators (PRGs), k-wise uniformity, small-bias generators, Boolean Fourier analysis, decision trees, width-2 branching programs, Viola's PRG for low-degree polynomials over GF(2). [Suggested reading: HH sections 1.0-2.4; Vadhan sections 1.1, 1.2, 2.3.4, 3.5.1, 3.5.2, and 3.5.5.]

    1. Tuesday 9/26:
    2. Thursday 9/28:
    3. Tuesday 10/3:
    4. Thursday 10/5:

    Part II: Expanders and Extractors. Tentative topic list: The L vs. BPL problem, read-once branching programs, spectral expander graphs, the Impagliazzo-Nisan-Wigderson PRG, the derandomized squaring operation, Reingold's theorem, randomness extractors, the Nisan-Zuckerman PRG, the Guruswami-Umans-Vadhan extractor, randomness-efficient sampling.

    1. Tuesday 10/10:
    2. Thursday 10/12:
    3. Tuesday 10/17:
    4. Thursday 10/19:
    5. Tuesday 10/24:
    6. Thursday 10/26:

    Part III: Circuits. Tentative topic list: The P vs. BPP problem, the Sipser-Gacs-Lautemann theorem, Adleman's theorem, circuit lower bounds, bounded-depth circuits, the Nisan-Wigderson PRG, the sandwiching lemma, Braverman's theorem.

    1. Tuesday 10/31:
    2. Thursday 11/2:
    3. Tuesday 11/7:
    4. Thursday 11/9:

    Part IV: Random Restrictions. Tentative topic list: Switching lemmas, PRGs from polarizing random walks, the Ajtai-Wigderson PRG framework, arbitrary-order read-once branching programs, the Forbes-Kelley PRG, the Impagliazzo-Meka-Zuckerman PRG.

    1. Tuesday 11/14:
    2. Thursday 11/16:
    3. (No class on 11/21 or 11/23 due to Thanksgiving Break)
    4. Tuesday 11/28:
    5. Thursday 11/30:
    6. Tuesday 12/5:
    7. Thursday 12/7:

    Texts We will use the following two texts, each of which is available for free online.

    Grading 65% problem sets, 25% project, 10% participation.

    Problem Sets There will be four proof-based problem sets throughout the quarter. Submit your solutions through Canvas.

    Collaboration. You are encouraged to collaborate with your classmates on problem sets, but you must adhere to the following rules.

    Permitted Resources for Full Credit. Beyond discussions with me and discussions with classmates as discussed above, you may use the course texts and any notes that might be posted on this webpage. If you wish to receive full credit on a problem, you may not use any other resources.

    Outside Resources for Partial Credit. If you wish, you may use outside resources (Wikipedia, ChatGPT, Stack Exchange, research papers, etc.) to solve a problem for partial credit. If you decide to go this route, you must make a note of which outside resources you used when you were working on each problem. You must disclose using a resource even if it was ultimately unhelpful for solving the problem. Furthermore, if you consult an outside resource while working on a problem, then you must not discuss that problem with your classmates.

    Late Submissions. Late work will receive partial credit. Specifically, if you turn in a problem set \(x\) days late, where \(0 < x < 5\), then your score will be multiplied by \(\cos^2(\frac{\pi x}{10})\), with some rounding. The value \(x\) can be fractional. Saturdays, Sundays, and university holidays are all excluded from the lateness calculation. If you give me sufficiently early notice that you will be observing a religious holiday, then that day will also be excluded from the lateness calculation. Work turned in five or more days late will not receive any credit.

    Project Pseudorandomness is an active area of research. There are many important theorems in this area that we won't have time to cover in class, including lots of exciting recent work!

    You will study one such theorem and write an exposition. You will explain what the theorem means and why it matters, and you will explain some or all of the proof.

    You can select your theorem from a list that will be provided, or, with permission, you can choose a theorem that is not on the list. Further details TBA.

    Academic Honesty Catch-All Policy Students frequently find themselves in "gray area" situations that are not clearly covered by course policies. For example, maybe you accidentally stumble upon the solution to a homework problem while reading the textbook for a different course.

    In such circumstances, you should simply write a note explaining what happened and include it with your submission.

    I encourage you to follow this simple protocol in every course you take. It is a surefire way to avoid getting in trouble for academic dishonesty. Depending on the circumstances, you might receive a grade penalty, but don't let this deter you. A clean conscience is worth more than any grade.

    Accessibility and Accommodations I want all students to be able to fully participate in this course. Let me know if you need an accommodation for any reason, so we can explore possible solutions together. If applicable, please follow the protocols established by UChicago Student Disability Services.

    To highlight one example, I am happy to work with students who are pregnant/parenting to figure out the best way to make the course work for you.

    Inclusion and Atmosphere This course, like every course you take, ought to be an enjoyable and enriching experience. You have a right to be treated with respect and a responsibility to treat others with respect.

    To highlight one facet of this topic, you are encouraged to ask questions in class, and you should make your classmates feel comfortable asking questions in class. There is no shame in not knowing something or not understanding something. Questions make the course better for everyone.

    To highlight another facet, computer scientists can come from many diverse backgrounds, and nobody should experience prejudice or discrimination in this course.