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 will be a one-time review session for concentration inequalities at Friday Feb 6, 2pm in room 24-310. Please feel free to come and ask questions about these or any probability theory topics. If you can't make it, the material covered will be the same as in the "concentration inequalities reference" linked under Useful Information below, and you can always ask questions on Piazza.

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]

Note: Future lecture contents are tentative.

(2/12) Lecture 4 (Lily): Finish Moser's algorithm. Markov chains and random walks: Stationary distributions, cover times. [handwritten notes] and [scribe notes]
(2/17) Monday schedule, no lecture.
(2/19) Lecture 5: Undirected s-t connectivity, space-bounded computation. Saving random bits via random walks. Linear algebra and expanders. [handwritten notes] and [scribe notes]
(2/24) Lecture 6: Random walks and expanders continued. Expander mixing lemma, amplification. [handwritten notes] and [scribe notes]
(2/26) Lecture 7 (Guest lecture with Ted Pyne): Pseudorandom generators, Impagliazzo-Nisan-Wigderson PRG. Directed random walks in deterministic log² space.

Homework:

Homework submission: link [coming soon]

Homework 1. Posted February 3, 2026. Due February 18.

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 [coming soon] for graders.