6.842 Randomness and Computation

Instructor: Ronitt Rubinfeld
Time: MW 1:00-2:30
Place: 36-155
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, random variables with limited independence, Fourier analysis, testing properties of boolean functions, the influence of variables, random walks. (2) Randomness in various computational settings: algorithms, computational learning theory, communication complexity, probabilistic proofs, complexity theory. (3) Generating randomness: pseudorandom generators, derandomization, graph expansion, extractors.

Lecture Notes


Useful information