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 (williamhoza@uchicago.edu)

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

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

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. Suggested reading: HH sections 1.0-2.3; Vadhan sections 1.1, 1.2, 2.3.4, 3.5.1, 3.5.2, and 3.5.5.

1. Tuesday 9/26: Course overview [slides], PRG definition, pairwise uniform bits [notes].
2. Thursday 9/28: Derandomizing max cut, k-wise uniform bits, shallow decision trees, the triangle inequality for PRG errors.
3. Tuesday 10/3: Probabilistic existence proof for PRGs, explicitness, $\varepsilon$-biased generators, Boolean Fourier expansion, Fourier $L_1$ norm.
4. Thursday 10/5: $L_1$ bounds for decision trees and juntas, $k$-wise $\varepsilon$-biased generators, $\varepsilon$-almost $k$-wise uniform generators.

Part II: Expanders. Suggested reading: Vadhan sections 2.4 and 4.0-4.3; HH sections 3.0-3.2; this paper by Rozenman and Vadhan.

5. Tuesday 10/10: Random walks in graphs, the quantity $\lambda(G)$, undirected $s$-$t$ connectivity in randomized log space, the L vs. BPL problem.
6. Thursday 10/12: The PRG characterization of expanders, the expander mixing lemma, explicit expander constructions.
7. (Problem set 1 due on Friday 10/13)
7. Tuesday 10/17: Expander graphs from small-bias distributions, the INW generator.
8. Thursday 10/19: Random walks in expander graphs, the hitting property of expander walks.
9. Tuesday 10/24: The expander decomposition lemma, the derandomized squaring operation [paper], beginning of the proof of Reingold's theorem.
10. Thursday 10/26: End of the proof of Reingold's theorem, total variation distance.
11. (Problem set 2 due on Friday 10/27)

Part III: Extractors. Suggested reading: Vadhan sections 2.3.1, 3.5.4, and 6.0-6.2; HH section 3.4.

11. Tuesday 10/31: Min-entropy, seeded extractors, simulating BPP with a weak random source, randomness-efficient samplers.
12. Thursday 11/2: Equivalence between extractors and averaging samplers, explicit construction of extractors based on $k$-wise uniformity.
13. Tuesday 11/7: Conditional min-entropy, the data processing inequality, the Nisan-Zuckerman PRG.
14. (Problem set 3 due on Wednesday 11/8)

Part IV: Hardness vs. Randomness. Suggested reading: Vadhan sections 2.2.0-2.2.2 and 3.1-3.3; HH chapter 4, section 5.0, and section 5.6.

14. Thursday 11/9: End of the analysis of the Nisan-Zuckerman PRG, P/poly, Adleman's theorem, PRGs imply hardness.
15. Tuesday 11/14: Hardness for ROBPs, hardness for $\mathrm{AC}^0$ circuits, average-case hardness, the distinguisher-to-predictor lemma.
16. Thursday 11/16: Finishing the proof of the distinguisher-to-predictor lemma, nearly disjoint sets, the Nisan-Wigderson PRG, fooling $\mathrm{AC}^0$ circuits.
17. (Problem set 4 due on Friday 11/17)
18. (No class on 11/21 or 11/23 because of Thanksgiving Break)
19. (No class on 11/28 because I will be out of town)
17. Thursday 11/30: Unrestricted branching programs, random restrictions, shrinkage, the IMZ generator, course review [slides].
18. (Project due on Tuesday 12/5)

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

• "Theory of Unconditional Pseudorandom Generators" by Hatami and Hoza. Please let me know if you find any mistakes in this text!
• "Pseudorandomness" by Vadhan.

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.

1. Problem set 1, due October 13 at 5pm
2. Problem set 2, due October 27 at 5pm [typo corrected on 10/24]
3. Problem set 3, due November 8 at 5pm
4. Problem set 4, due November 17 at 5pm

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

• Before discussing a problem with a classmate, you must work on the problem on your own for at least 20 minutes.
• You must ultimately write your solution on your own. While writing your solution, you may not consult any notes that you took during a discussion with another classmate.
• In your write-up, you must list any classmates who contributed to your solution through discussion. The fact that A contributed to B's solution does not necessarily mean that B contributed to A's solution.

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 posted in the "Course Timeline" section of 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!

For your project, choose one theorem from this list. Study the theorem and its proof (see the references in the topic list), then write an exposition.

Your exposition should explain what the theorem says and why the theorem is important. Your exposition should also explain the proof of the theorem, but this explanation need not be complete. For example, you might choose to only explain part of the proof, or you might choose to prove a special case of the theorem. I encourage you to try to develop and explain a new way of thinking about the proof. Your exposition should be in the ballpark of 5-10 pages, but there are no strict page limits.

(If you get permission, then your project may deviate from the plan described above. For example, maybe you would like to study a theorem that is not on the list.)

Submit your exposition via Canvas. The deadline is Tuesday, December 5 at noon.

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.