Class times: Monday & Wednesday 12:45pm-2pm (over lunch)
Class location: SEC 1.307
Instructor: Salil Vadhan (he/they)
http://salil.seas.harvard.edu/, salil_vadhan@harvard.edu
Office hours posted at salil.seas.harvard.edu. Most weeks Tue 1:45pm-2:30pm on Zoom and Fri 10:45am-11:30am in person. Usually also available for 15-30min after each seminar meeting.
Teaching Fellow: Jake Ruotolo (he/him)
jakeruotolo@g.harvard.edu
Office hours TBD
This is a seminar-style course, aimed at preparing students to engage in and benefit from the Fall 2026 program on Pseudorandomness and High-Dimensional Expansion to be held at the Simons Institute for the Theory of Computing at UC Berkeley. The focus will be on reading, presenting, and brainstorming about recent research papers in these fields, as well as acquiring any background needed to do so.
Pseudorandomness is the theory of efficiently generating random-like objects using little or no randomness. Defining “random-like” in different ways gives different notions of pseudorandomness that have been useful in a variety of different areas of computer science and mathematics. Such areas extend well beyond the original motivation of derandomization, and include computational complexity, algorithms, cryptography, communication, and combinatorics. The main objects of study are pseudorandom generators of various kinds, randomness extractors, expander graphs, and error-correcting codes. Pseudorandomness has been a subfield of theoretical computer science for over four decades, and there continues to be progress on fundamental open questions.
High-Dimensional Expansion (HDX) is a generalization of expansion in graphs to higher dimensions. Graph expansion is a key concept in computer science and mathematics with a plethora of applications, from network design to error-correcting codes. The definition of high-dimensional expansion is not complicated, yet it is not the first definition that comes to mind. In fact, many generalizations of expansion from graphs to hypergraphs have been studied over the years, but none of those definitions are as powerful as the relatively new definitions of local spectral expansion and coboundary expansion. The area of high dimensional expansion is still in relatively early stages, as definitions are stabilizing and new connections are being discovered. We are witnessing a flow of exciting results in areas ranging from convergence of Markov chains, to topology, to error correcting codes, and even PCPs.
This seminar is aimed at students who are already involved in or are ready to get engaged with research in theoretical computer science. Thus, we expect you to have already taken at least one graduate-level course in theoretical computer science (CS 22xx) or a closely related area of mathematics. If you do not meet this requirement, you must come talk to Salil in office hours during the first week of the class to help determine whether the class is appropriate for you.
Students will be expected to:
Read (assigned portions of) all of the papers being covered, commenting on them using the social e-reader Perusall. (Approximately 2 hours per class meeting.)
Present or co-present some papers in class and run the discussion on those papers.
Regularly attend class meetings and be an active participant in the discussions of papers.
A more quantitative specification of requirements will be given as the enrollment becomes clear. You can miss up to 4 classes and up to 4 classes worth of commenting without penalty; for flexibility beyond that, write to the course staff with your Resident Dean (for undergraduates) or advisor (for graduate students) in cc .
By the end of the course, we hope that you will all be able to:
Understand (some of) the state of the art in pseudorandomness and high-dimensional expansion as needed to engage in research in these areas and/or apply it to other areas,
Read and critically evaluate current research papers in these areas, extracting both high-level ideas and low-level details, and identifying interesting research questions that come out of them,
Effectively present research papers to your peers, in a way that is clear, informative, and efficient, and
Engage in a collaborative learning and brainstorming process with your peers.
We would like to create a learning environment in our class that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, ability, etc.). We (like many people) are still in the process of learning about diverse perspectives and identities. If something was said in class (by anyone) that made you feel uncomfortable, please talk to us about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please don’t hesitate to come and talk with us. As a participant in course discussions, you should also strive to be open-minded and respectful of your classmates.
If you have a physical or mental health condition that affects your learning or classroom experience, please let us know as soon as possible so that we can do our best to support your learning (at minimum, providing all of the accommodations listed in your DAO letter if you have one).
Everyone can benefit from support during challenging times. Not only are we happy to listen and make accommodations as needed, we can also refer you to additional support structures on campus, including, but not limited to, the below.
Counseling and Mental Health Services, 617-495-2042
Harvard College Peer Counseling, 617-495-4969