- Instructor: Ronitt Rubinfeld
- Time: MW 11:00-12:30
- Place: 4-261

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

- (09/06) Lecture 1: Introduction. The probabilistic method (examples: hypergraph coloring, sum-free subsets). Begin the Lovasz Local Lemma? [scanned notes] and [scribe notes]
- (09/11) Lecture 2: The Lovasz Local Lemma. Example: hypergraph coloring revisited. Moser-Tardos Algorithm for finding solutions guaranteed by LLL. [scanned notes] and [scribe notes]
- (09/13) Lecture 3: Finish Moser-Tardos Algorithm. (see handwritten notes from last time) and [scribe notes] [latex]
- (09/18) Lecture 4: Randomized complexity classes. Derandomization via enumeration. Pairwise independence and derandomization (example: max-cut). [scanned notes] and [scribe notes] [latex]
- (09/20) Lecture 5: Pairwise independent hash functions. 2-point sampling. Interactive proofs. The class IP. Graph nonisomorphism is in IP. [scanned notes] and [scribe notes] [latex]
- (09/25) Lecture 6: IP models with public versus private coins. A protocol for lower bounding the size of the set (using pairwise independent hashing). [scanned notes] [scribe notes] [lec6-7-scribe notes]
- (09/27) Lecture 7: Continued last lecture. [lec6-7-scribe notes]
- (10/1) Lecture 8: Derandomizing via the method of conditional expectations. Intro to Markov chains and random walks on graphs. [scanned notes]
- (10/4) Lecture 9: Random Walks, Stationary Distribution, Cover Times. [scanned notes] [scribe notes]
- (10/11) Lecture 10: times (continued). Undirected st-connectivity is in RL. Linear algebra and mixing times. Saving randomness via random walks. [scanned notes] [scribe notes] latex
- (10/16/) Lecture 11: Reducing Randomness via Random Walks on Special Graphs [scanned notes] [scribe notes]
- (10/18) Lecture 12: Undirected S-T Conn revisited (deterministic logspace) [scanned notes] [scribe notes] [latex]
- (10/23) Lecture 13: Szemeredi's Regularity Lemma; Testing dense graph property of triangle-freeness [scanned notes]
- (10/25) Lecture 14: Testing triangle-freeness [scanned notes] [scribe notes] [latex]
- (10/30) Lecture 15: Linearity Testing, Self-Correcting, Begin Fourier Analysis of Boolean Functions [scanned notes]
- (11/6) Lecture 16: Begin learning (see lec 18 for notes)
- (11/8) Lecture 17: The low degree algorithm (see lec 18 for notes), Fourier concentration
- (11/13) Lecture 18: Noise sensitivity and Fourier Concentration. Linear Threshold functions. [scanned notes]
- (11/15) Lecture 19: Learning large Fourier coefficients. [scanned notes]
- (11/20) Lecture 20 (Lecture 19 Continued): Learning large Fourier coefficients. [scanned notes]
- (11/22) Lecture 21: Weakly learning monotone functions [scanned notes] [scribe notes]
- (11/27) Lecture 22: Weak vs. strong learning, boosting [scanned notes] [scribe notes] [latex] [preamble-latex]
- (11/29) Lecture 23: (Lecture 22 continued): Weak vs. strong learning, boosting [scanned notes]
- (12/4) Lecture 24: (Lecture 22 continued): Weak vs. strong learning, boosting [scanned notes]
- (12/6) Lecture 25: Amplifying hardness. Yao's XOR lemma [scanned notes] [scribe notes] [latex]
- (12/11) Lecture 26: NP has probabilistically checkable proof systems requiring only constant queries[scanned notes]

- Homework 1. Posted September 11, 10am. Last update September 11, 10am. Due September 18. NOTE: ONE WEEK EXTENSION ON PROBLEM 3! Problem 3 now due on September 25. Hint for problem 1. Solutions: problem 1. problem 2. problem 3.
- Homework 2. Posted September 18, 2017 at 11:12am. Due September 25, 2017. Hint for problem 2. Solutions: problem 2.
- Homework 3. Posted September 25, 2017 at 11:22am. Last update October 1, 8:00pm. Due October 2, 2017 Hint for problem 2. Solutions: problem 1. problem 2.
- Homework 4. Posted October 4, 2017 at 3:30pm. Due October 11. Hint. Solutions: problem 1
- Homework 5. Posted October 18, 2017. Due October 25. EXTENSION ON PROBLEM 2 to October 30. Last update October 24, 6:30 pm. Hint for problem 2. Solutions: problem 1 problem 2
- Homework 6. Solutions: problem 1 problem 1 (latex) problem 2 problem 3 problem 3 (latex) Posted October 30, 2017. Due November 13.
- Homework 7. Posted November 21, 2017. Due December 4.

- (9/5) 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.

- Instructions for graders.