6.842 Randomness and Computation (Fall 2017)

Instructor: Ronitt Rubinfeld
Time: MW 11:00-12:30
Place: 4-261


  • Fourth homework is posted! (see below)
  • 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, Lovasz 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.

    Lecture Notes


    Useful information