6.842 Randomness and Computation (Spring 2014)

Instructor: Ronitt Rubinfeld
Teaching Assistant: Badih Ghazi
Time: MW 1:00-2:30
Place: 36-112


Weekly Office Hours: Monday 3:00-4:00pm, Room 32-G531.

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

Stellar site

See this place in order to turn in homeworks!