6.842 Randomness and Computation, Spring 2008

6.842 Randomness and Computation

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.

References on Markov, Chebyshev and tail inequalities:
- Avrim Blum's Handout on Tail inequalities.
- Avrim Blum's Handout on probabilistic inequalities.
- Jin Yi Cai's book containing derivations of useful probabilistic inequalities (see pages 63-67).
For future scribes, here is a sample file and the preamble.tex file that it uses. Please get a first draft to Krzysztof (konak with the usual csail and mit e-mail ending) within two days of the lecture. When using the definition environment, make sure to emphasize the term being defined.
Scribe schedule (Sign up, please!)
Grading
Mailing list: If you haven't received any email yet, you are not on the mailing list. Ask Krzysztof to add you.

Handouts

(02/06) Course Information [pdf] [ps]
(02/11) Problem Set 1, due 02/25 [pdf] [ps] Hint for Problem 4
(02/27) Problem Set 2, due 03/10 [pdf] [ps]
(03/13) Problem Set 3, due 04/02 [pdf] [ps]
(04/09) Problem Set 4, due 04/23 [pdf] [ps]
(04/28) Problem Set 5, due 05/07 [pdf] [ps] Hint for Problem 1

Lecture Notes

(02/06) Lecture 1: Polynomial identity testing with applications. [pdf] [ps] [tex]
(02/11) Lecture 2: Probabilistic method, linearity testing, and Fourier analysis. [pdf] [ps] [tex]
(02/13) Lecture 3: Linearity testing and Fourier analysis (cont'd). [pdf] [ps] [tex]
(02/19) Lecture 4: Testing dictator functions. Arrow's impossibility theorem. [pdf] [ps] [tex]
(02/20) Lecture 5: Introduction to learning. Learning via Fourier Coefficients. [pdf] [ps] [tex]
(02/25) Lecture 6: Learning via Fourier Coefficients: the Low Degree Algorithm. [pdf] [ps] [tex]
(02/27) Lecture 7: Learning halfspaces and intesections of halfspaces. [pdf] [ps] [tex]
(03/03) Lecture 8: Learning noisy parities. [pdf] [ps] [tex]
(03/05) Lecture 9: Learning heavy Fourier coefficients with queries. [pdf] [ps] [tex]
(03/10) Lecture 10: Learning decision trees and monotone functions with queries. [pdf] [ps] [tex]
(03/12) Lecture 11: Boosting. [pdf] [ps] [tex]
(03/17) Lecture 12: Boosting (cont'd). (see the notes for Lecture 11)
(03/19) Lecture 13: Yao's XOR Lemma. Models of computation vs. derandomization. [pdf] [ps] [tex]
(03/31) Lecture 14: Simple derandomization techniques. [pdf] [ps] [tex]
(04/02) Lecture 15: Random walks. [pdf] [ps] [tex]
(04/07) Lecture 16: Random walks, eigenvalues and mixing time. [pdf] [ps] [tex]
(04/09) Lecture 17: Derandomization via random walks. [pdf] [ps] [tex]
(04/14) Lecture 18: Undirected connectivity in LOGSPACE. [pdf] [ps] [tex]
(04/16) Lecture 19: The Nisan pseudorandom generator for bounded-space computation. [pdf] [ps] [tex]
(04/23) Lecture 20: The Nisan pseudorandom generator (cont'd) and its applications. [pdf] [ps] [tex]
(04/28) Lecture 21: Weakly random sources and extractors.
(04/30) Lecture 22: The Leftover Hash Lemma and explicit extractors.
(05/05) Lecture 23: Computational indistinguishability and pseudorandom generators.
(05/07) Lecture 24: Efficient pseudorandom generators, one-way functions, and one-way permutations.
(05/12) Lecture 25: Efficient pseudorandom generators, one-way functions, and one-way permutations (cont'd).
(05/14) Lecture 26: The Nisan-Wigderson pseudorandom generator. Trevisan's extractor. (No notes for this lecture.)
Drafts of lecture notes