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

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

- (02/05) Lecture 1: Introduction. The probabilistic method (examples: hypergraph coloring, sum-free subsets). Begin the Lovasz Local Lemma. [scanned notes] and [scribe notes]
- (02/10) Lecture 2: The Lovasz Local Lemma. Example: hypergraph coloring revisited. Moser-Tardos Algorithm for finding solutions guaranteed by LLL. [scanned notes] and [scribe notes]
- (02/12) Lecture 3: Randomized complexity classes. Derandomization via enumeration. Pairwise independence and derandomization (example: max-cut). [scanned notes] and [scribe notes]
- (02/18) Lecture 4: Pairwise independent hash functions. A construction. 2-point sampling. Interactive proofs. The class IP. Graph nonisomorphism is in IP. [scanned notes] and [scribe notes]
- (02/19) Lecture 5: IP models with public versus private coins. A protocol for lower bounding the size of the set (using pairwise independent hashing). Derandomizing via the method of conditional expectations. [scanned notes] and [scribe notes]
- (02/24) Lecture 6: Intro to Markov chains and random walks on graphs. Stationary distributions. Cover times. [scanned notes] and [scribe notes]
- (02/26) Lecture 7: Cover times (continued). Undirected st-connectivity is in RL. [scanned notes] and [scribe notes]
- (03/03) Lecture 8: Linear algebra and mixing times. Saving randomness via random walks. [scanned notes] and [scribe notes]
- (03/5) Lecture 9: s-t connectivity in deterministic logspace [scanned notes] and [scribe notes]
- (03/10) Lecture 10: Szemeredi's Regularity Lemma; Application to testing triangle freeness in dense graphs. [scanned notes] and [scribe notes]
- (03/12) Lecture 11: Fourier basics. Plancherel's and Parseval's theorems. Linearity testing. [slides] and [scribe notes]
- (03/17) Lecture 12: Learning under the uniform distribution. Model. Brute force algorithm. Learning conjunctions. Estimating one Fourier coefficient. [scanned] and [scribe notes]
- (03/19) Lecture 13: Fourier representations for basic functions. Learning via the Fourier representation -- the low degree algorithm. Applications of the low degree algorithm. Learning AC0 functions. [scanned] and [scribe notes]
- (03/31) Lecture 14: Noise sensitivity and Fourier concentration. Applications to learning linear threshold functions. [scanned]
- (04/02) Lecture 15: Learning parity with noise using queries: The Goldreich-Levin algorithm [scanned] and [scribe notes]
- (04/07) Lecture 16: Weak learning of monotone functions. Begin strong learners from weak learners: Boosting algorithms. [scanned] and [scribe notes]
- (04/09) Lecture 17: Continue boosting algorithms [scanned] and [scribe notes]
- (04/14) Lecture 18: More Boosting. [scanned] and [scribe notes]
- (04/16) Lecture 19: Boosting and complexity theory: Amplifying hardness. Yao's XOR lemma. [scanned] and [scribe notes]
- (04/23) Lecture 20: Pseudorandomness. Computational Indistinguishability. [scanned] and [scribe notes]
- (04/28) Lecture 21: Pseudorandomness. Computational Indistinguishability. (Continued) [scanned]
- (04/30) Lecture 22: Pseudorandomness vs. next bit unpredictability. One way functions. [scanned]
- (05/05) Lecture 23: One way permutations and pseudo-random generators. Hardcore bits. [scanned]
- (05/07) Lecture 24: Hardness vs. randomness. The Nisan-Wigderson pseudo-random generator. [scanned]
- (05/12) Lecture 25: Weak Random Sources. Randomness Extractors. [scanned]
- (07/12) Lecture 26: Weak Random Sources. Randomness Extractors. (Continued) [scanned]

- Homework 1. Posted February 4, 1pm. Last update February 4, 1pm. Due February 12.
- Homework 2. Posted February 12, 10pm. Last update February 12, 10pm. Due February 19.
- Homework 3. Posted February 19, 9pm. Last update February 19, 9pm. Due February 26.
- Homework 4. Posted February 26, 8pm. Last update February 26, 8pm. Due March 5.
- Homework 5. Posted March 5, 11pm. Last update March 11, 4pm. Due March 12.
- Homework 6. Posted March 12, midnight. Last update March 13, 8pm. Due March 19.
- Homework 7. Posted March 20, 4pm. Last update March 20, 4pm. Due April 2.
- Homework 8. Posted April 3, 8pm. Last update April 3, 8pm. Due April 10.
- Homework 9. Posted April 10, 10pm. Last update April 12, 1pm. Due April 17.
- Homework 10. Posted April 21, 11pm. Last update April 22, 2pm. Due April 28. Homework 11 (Optional). Posted May 7, 5pm. Last update May, 5pm. Due May 14.
- Solutions

- (02/04) Course Information [pdf]
- References on Markov, Chebyshev and tail inequalities:
- Avrim Blum's Handout on Tail inequalities.
- Avrim Blum's Handout on probabilistic inequalities.

- Texts:
- Salil Vadhan's Pseudorandomness.
- Ryan O'Donnell's Analysis of Boolean Functions.

- Information for scribes:
- Here is a sample file and the preamble.tex file that it uses. Please get a first draft to me within two days of the lecture. When using the definition environment, make sure to emphasize the term being defined.
- Here are some tips.