6.842 Randomness and Computation

Instructor: Ronitt Rubinfeld
Teaching Assistant: Krzysztof Onak
Time: MW 2:30-4:00
Place: 34-304
3-0-9 H-Level Grad Credit
Brief Course description: The power and sources of randomness in computation. Connections and applications to computational complexity, computational learning theory, cryptography and combinatorics. Topics include: (1) Basic tools: polynomial zero testing, uniform generation and approximate counting, Fourier analysis, testing properties of boolean functions, the influence of variables, random walks. (2) Randomness in various computational settings: computational learning theory, communication complexity, probabilistic proofs, complexity theory. (3) Generating randomness: pseudorandom generators, derandomization, graph expansion, extractors.


Lecture Notes