- Instructor: Ronitt Rubinfeld
- Teaching Assistant: Matthew Menke
- Time: MW 2:30-4:00
- Place: 36-112
- 3-0-9 H-Level Grad Credit

**Office hours:** By appointment.

- On Monday 5/8 4:15 in G575, Tali Kaufman will speak on property testing of codes.
- Makeup lecture: Friday, May 12, 2:30-4, G575 (theory lab).
- There were a few people that wanted references to Markov chains. Here are some suggestions given by random people: text by Feller "Introduction to Probability Theory and its Applications" (Vol 1), Mitzenmacher and Upfal's "Randomized Algorithms and Probabilistic Analysis" , the book by Aldous (can be found on the web), the wikipedia entry and the links given there.

- General Course Information (including contact information, more detailed syllabus)

- 02/8: Introduction. Equality testing of polynomials with applications to bipartite matching. Probabilistic proofs. (tex file) , (pdf version) , (ps version)
- 02/13: More probabilistic proofs: Linearity testing. Random self-reducibility/self-correcting programs. (tex file) , (pdf version) , (ps version)
- 02/15: More linearity testing. Begin introduction to Fourier analysis on Boolean cube. (tex file) , (pdf version) , (ps version)
- 02/21: Introduction to Fourier analysis on Boolean cube. Application to linearity testing. (tex file) , (pdf version) , (ps version)
- 02/22: Learning functions with sparse Fourier representation. (tex file) , (pdf version) , (ps version)
- 02/27: Learning constant depth circuits. Learning decision trees. (tex file) , (pdf version) , (ps version)
- 03/1: Learning decision trees. Weakly learning monotone functions. (tex file) , (pdf version) , (ps version)
- 03/6: Uniform generation of DNF assignments. (tex file) , (pdf version) , (ps version)
- 03/8: Uniform generation and approximate counting. (tex file) , (pdf version) , (ps version)
- 03/13: Random walks. (tex file) , (ps version)
- 03/15: st-connectivity. Uniform generation via random walks on large Markov chains. Generating random spanning trees. (ps version)
- 03/20: Generating random spanning trees. Preliminary definitions of conductance. (pdf version) (ps version) (texversion)
- 03/22: Conductance. Generating random matchings of a graph. (pdf version) (ps version) (texversion)
- 04/3: Finish generating random matchings of a graph. (pdf version) (ps version) (texversion)
- 04/5: Mixing time and Eigenvalues. Saving random bits via random walks on expanders. (tex version) , (ps version) , (pdf version)
- 04/10: Finish saving random bits via random walks on expanders. Begin discussion of pairwise independence. (tex version) , (ps version) , (pdf version)
- 04/19: Pairwise independence. Use in algorithms. Constructing pairwise independent random bits/numbers. (tex version) , (ps version) , (pdf version)
- 04/24: Reingold's Algorithm for s-t connectivity in deterministic logspace. (tex version) , (ps version) , (pdf version)
- 04/26:
- 05/1:
- 05/3: PRGs and BPP. PRG's and unpredictability. (tex version) , (ps version) , (pdf version)
- 05/8: Impossibility of deterministic Byzantine agreement in asynchronous communication model. (guest lecturer: Vinod Vaikuntanathan)
- 05/10: Possibility of randomized Byzantine agreement in asynchronous communication model. (guest lecturer: Vinod Vaikuntanathan)
- 05/12: (optional makeup lecture) One way permutations and PRGs. Discussion of why we have already seen the details behind the existence of hardcore bits (Goldreich Levin).
- 05/15: (Nisan-Wigderson).

- If you are not familiar with Markov, Chebyshev and Hoeffding/Chernoff bounds, please read about them in one or more of the descriptions given in useful pointers.
- Problem set 1 Handed out 2/21, due 3/6. Hint for problem 5 , Solutions.
- Problem set 2. Handed out 3/6, due 3/20.
- Problem set 3. Handed out 3/20, due 4/10. Hint for problem 1
- Problem set 4. Handed out 4/10, due 4/24.
- Problem set 5. Handed out 5/1, due 5/12. (Note -- earlier than usual due date). Hint for problem 5

- 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 Matt (mmenke with the usual 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