6.5420 Randomness and Computation (Spring 2026)
- Instructor:
Ronitt Rubinfeld
- 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: By appointment.
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 log2 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]
- (3/31) Lecture 13:
More on linearity testing and Fourier analysis. Learning boolean functions.
[handwritten notes] and
[scribe notes]
- (4/2) Lecture 14:
Learning boolean functions, continued.
[handwritten notes] and
[scribe notes]
- (4/7) Lecture 15:
Fourier-based learning algorithms, Fourier concentration.
[handwritten notes] and
[scribe notes]
- (4/14) Lecture 16:
Fourier-based learning algorithms continued, noise sensitivity.
[handwritten notes] and
[scribe notes]
- (4/16) Lecture 17:
Fourier learning and noise sensitivity continued.
[handwritten notes] and
[scribe notes]
- (4/21) Lecture 18:
Learning heavy Fourier coefficients.
[handwritten notes] and
[scribe notes]
- (4/23) Lecture 19:
Weak learning of monotone functions. Intro to boosting.
[handwritten notes] and
[scribe notes]
Note: Future lecture contents are tentative.
Homework:
Homework submission: Gradescope (details on Piazza).
Useful information:
- References on Markov, Chebyshev and tail inequalities:
- Texts:
- Information for scribes:
-
Instructions for graders.
Signup for graders: Link on Piazza.