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)

Lectures: Tuesdays and Thursdays, 11:00-12:30 in 32-144

Office hours: Fridays at 4pm in 32-G634

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:

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.
(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]
(3/3) Lecture 7: Saving random bits in amplification using expanders. [handwritten notes] and [scribe notes]
(3/5) Lecture 8: Pairwise independence: Derandomizing max-cut. Generating pairwise independent bits. [handwritten notes] and [scribe notes]
(3/10) Lecture 9: More pairwise independence: Reducing randomness in amplification. Interactive proofs, Goldwasser-Sipser protocol. [handwritten notes] and [scribe notes]
(3/12) Lecture 10: Derandomization via the method of conditional expectations. Uniform generation of satisfying assignments to DNF formulae. Counting problems. [handwritten notes] and [scribe notes]
(3/17) Lecture 11: The complexity of uniform generation vs. the complexity of counting. [handwritten notes] and [scribe notes]
(3/19) Lecture 12: Linearity testing and Fourier analysis on the hypercube. [handwritten notes] and [scribe notes]

Note: Future lecture contents are tentative.

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.
Homework 3. Posted March 7, 2026. Due March 18.
Homework 4. Posted March 19, 2026. Due April 15.

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.