- 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]
- (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]
- (10/16/) Lecture 11: Reducing Randomness via Random Walks on Special Graphs [scanned notes]
- (10/18) Lecture 12: Undirected S-T Conn revisited (deterministic logspace) [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.
- 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.
- Homework 4. Posted October 4, 2017 at 3:30pm. Due October 11. Hint.

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