6.842 Randomness and Computation (Spring 2020)

Instructor: Ronitt Rubinfeld
Teaching Assistant: Amartya Shankha Biswas
Course email: 6842-sp20 csail mit edu (with at and dots in proper places)
Time: TTh 11:00-12:30
Place: 4-149 (NOTE NEW ROOM)

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.

Course Information Handout

Original course information sheet. Requirements and rubric overidden as FOLLOWS.

Announcements:

Lecture Notes:

Homework:

Useful information: