CMSC 39600: Derandomizing Space-Bounded Computation (Winter 2025)

Full Course Title: "Topics in Theoretical Computer Science: Derandomizing Space-Bounded Computation"

Term: Winter 2025 at the University of Chicago

Instructor: William Hoza (williamhoza@uchicago.edu)

Meetings: Tuesdays and Thursdays | 2:00pm - 3:20pm | JCL 011

Office Hours: Tuesdays | 3:30pm - 4:45pm | JCL 311

Jump to: (loading...)

    Course Description

    What is the relationship between space complexity and randomness? Both space and random bits can be considered "expensive" computational resources, so it is desirable to use as little of each as possible. One of the major goals of computational complexity theory is to prove that every randomized decision algorithm can be "derandomized" (i.e., converted into a deterministic algorithm) without increasing its space complexity by more than a constant factor. Complexity theorists have made a great deal of progress toward proving this conjecture over the past several decades, and it is an active and exciting area of research today. In this seminar course, we will study both classic and cutting-edge work on this problem and closely related problems. This will involve topics such as pseudorandom generators, expander graphs, Laplacian solvers, and the Fourier analysis of Boolean functions.

    This is a graduate-level, research-oriented course. My intention is that this course will prepare you to conduct original research on the derandomization of space-bounded computation. If you're an undergraduate student and you want to take this course, you'll need to discuss it with me and get approval. If you're a graduate student, there are no firm prerequisites, but it would be helpful to have some familiarity with computational complexity theory and probability theory. The course does not have a textbook per se, but the following surveys might be helpful:

    Course Timeline

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

    Tuesday 1/7: Random walks in undirected graphs; the expansion parameter $\lambda(G)$. Reading:
    Thursday 1/9: The complexity class $\mathsf{BPL}$; variants of the model; $\mathsf{BPL}$ algorithms run in polynomial time; expander graphs. Reading:
    Tuesday 1/14: The expander mixing lemma; the INW pseudorandom generator. Reading:
    Thursday 1/16: The expander decomposition lemma; the derandomized square operation; undirected connectivity is in $\mathsf{L}$. Reading:
    Tuesday 1/21: Undirected connectivity is in $\mathsf{L}$ (continued); standard-order ROBPs can be simulated by standard-order regular ROBPs. Reading (regarding the reduction to regular ROBPs):
    Thursday 1/23: The BRRY analysis of the INW generator on regular ROBPs; basics of Boolean Fourier analysis. Reading:
    Tuesday 1/28: Arbitrary-order ROBPs; the Forbes-Kelley PRG. Reading:
    Thursday 1/30: Small-bias generators; simplification of read-once CNFs under mild random restrictions; iterated restrictions with early termination; near-optimal PRGs for read-once CNFs. Reading:
    Tuesday 2/4: [Student presentations.]
    Thursday 2/6: [Student presentations.]
    Tuesday 2/11: [Student presentations.]
    Thursday 2/13:
    Tuesday 2/18:
    Thursday 2/20:
    Tuesday 2/25:
    Thursday 2/27:
    Tuesday 3/4:
    Thursday 3/6:
    Finals week:

    Student Presentations

    As part of this course, you will study two research papers on your own and present them to the class. The first presentation will be near the middle of the quarter, and the second presentation will be near the end of the quarter. You should think of your classmates as your target audience. Further details will be determined later, based in part on the number of students who enroll in the course.

    Each presentation should be 30-35 minutes, which will give us a few minutes for questions. For each presentation, I encourage you to pick just one theorem from your paper to focus on. Start your presentation by clearly explaining what the theorem says and why it matters. Then tell us something about the proof. You won't have enough time to present all the details of the proof, and that's okay. You could give us a high-level overview of the proof as a whole, or you could present a detailed proof of a single interesting lemma. You can use the whiteboard or you can use slides, whichever you prefer. I encourage you to practice your presentation at least once on your own time.

    You get to choose your papers from the two lists below, with the caveat that if two students choose the same paper, then one of them will need to do a different paper instead. (I will coordinate the paper selection process.) With approval, you can select papers that are not on the lists.

    You can use the UChicago library proxy server to access papers that are behind paywalls. I've linked to the most "official" versions available of the papers below, but you might want to also look for other versions, such as ECCC preprints.

    Round 1 (mid-quarter) presentation papers:

    Round 2 (end-of-quarter) presentation papers:

    Grading Policies

    Your grade will be based on class participation (34%) and your two presentations (33% each).

    Inclusion and Accessibility

    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. 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 a few facets of these topics: