- Instructor: Ronitt Rubinfeld
- Teaching Assistant: Krzysztof Onak
- Time: MW 2:30-4:00
- Place: 34-304
- 3-0-9 H-Level Grad Credit

- 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.

- (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

- (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