6.842 Randomness and Computation
Brief Course description:
The power and sources of randomness in computation.
Connections and applications to computational complexity,
computational learning theory, cryptography and combinatorics.
(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.
- Teaching Assistant:
- Time: MW 2:30-4:00
- Place: 34-304
- 3-0-9 H-Level Grad Credit
- References on Markov, Chebyshev and tail inequalities:
For future scribes, here is a
sample file and
the preamble.tex file that
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!)
- Mailing list: If you haven't received any email yet, you are not on the mailing list. Ask Krzysztof to add you.
- (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