6.5420 Randomness and Computation, Spring 2026

6.5420 Randomness and Computation (Spring 2026)

Teaching Assistant: Lily Chung

Course email: 6-5420-staff lists csail mit edu (with at and dots in proper places)

Time: Tuesdays and Thursdays, 11:00-12:30

Place: 32-144

Brief Course description:

We study the power and sources of randomness in computation, concentrating on connections and applications to computational complexity, computational learning theory, cryptography and combinatorics. Topics include:

(1) Basic tools: probabilistic, proofs, Lovász local lemma, uniform generation and approximate counting, Fourier analysis, influence of variables on functions, random walks, graph expansion, Szemeredi regularity lemma.

(2) Randomness vs. Predictability: pseudorandom generators, weak random sources, derandomization and recycling randomness, computational learning theory, Fourier based learning algorithms, weak vs. strong learning, boosting, average vs. worst case hardness, XOR lemma.

Course information handout.
Tentative pset and quiz dates.

Announcements:

There is a one day extension to pset 1: new due date is February 19.
Lily will hold office hours on Fridays at 4pm in room 32-G634. As always you can ask questions on Piazza if you cannot make it (please ask a private question if you need to discuss your solution).

Lecture Notes:

(2/3) Lecture 1: Introduction. Polynomial zero testing. Applications to astronaut-on-the-moon and bipartite matching problems. [handwritten notes] and [scribe notes]
(2/5) Lecture 2: The probabilistic method (examples: hypergraph coloring, dominating sets, sum-free sets). [handwritten notes] and [scribe notes]
(2/10) Lecture 3: The Lovasz Local Lemma. Example: hypergraph coloring revisited. Moser's algorithm for finding solutions guaranteed by LLL. [handwritten notes] and [scribe notes]
(2/12) Lecture 4 (Lily): Finish Moser's algorithm. Markov chains and random walks: Stationary distributions, cover times. Undirected st-connectivity is in randomized logarithmic space. [handwritten notes] and [handwritten notes part II] and [scribe notes]
(2/17) Monday schedule, no lecture.
(2/19) Lecture 5: Linear algebra and expanders. Expander mixing lemma. Randomized complexity classes. Derandomization via enumeration. [handwritten notes] and [scribe notes]
(2/24) Snow day, no lecture.
Note: Future lecture contents are tentative.
(2/26) Lecture 6 (Guest lecture with Ted Pyne): Pseudorandom generators, Impagliazzo-Nisan-Wigderson PRG. Directed random walks in deterministic log² space. [handwritten notes] and [scribe notes]

Homework:

Homework submission: Gradescope (details on Piazza).

Homework 1. Posted February 3, 2026. Due February 18. Hints for Homework 1
Homework 2. Posted February 20, 2026. Due March 4.

Useful information:

References on Markov, Chebyshev and tail inequalities:
- Lily's concentration inequalities reference.
- Avrim Blum's Handout on Tail inequalities.
- Avrim Blum's Handout on probabilistic inequalities.
Texts:
- Alon & Spencer, "The Probabilistic Method"; also Yufei Zhao's lecture notes
- Salil Vadhan's Pseudorandomness.
- Ryan O'Donnell's Analysis of Boolean Functions.
Information for scribes:
- Here is a sample file and the preamble.tex file that it uses.
- Here are some tips.
- Scribe signup: Link on Piazza.
Instructions for graders. Signup for graders: Link on Piazza.