## 6.895 Randomness and Computation

Instructor: Ronitt Rubinfeld
Teaching Assistant: Matthew Menke
Time: MW 2:30-4:00
Place: 36-112
Brief Course description: The power and sources of randomness in computation. Topics include: (1) Basic tools: polynomial zero testing, linearity testing, uniform generation and approximate counting, the influence of variables. (2) Randomness in various computational settings: computational learning theory,communication complexity, probabilistic proofs. (3) Generating randomness: pseudorandom generators, derandomization, expanders, extractors.

Office hours: By appointment.

### Announcements

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

### Lecture Notes

1. 02/8: Introduction. Equality testing of polynomials with applications to bipartite matching. Probabilistic proofs. (tex file) , (pdf version) , (ps version)
2. 02/13: More probabilistic proofs: Linearity testing. Random self-reducibility/self-correcting programs. (tex file) , (pdf version) , (ps version)
3. 02/15: More linearity testing. Begin introduction to Fourier analysis on Boolean cube. (tex file) , (pdf version) , (ps version)
4. 02/21: Introduction to Fourier analysis on Boolean cube. Application to linearity testing. (tex file) , (pdf version) , (ps version)
5. 02/22: Learning functions with sparse Fourier representation. (tex file) , (pdf version) , (ps version)
6. 02/27: Learning constant depth circuits. Learning decision trees. (tex file) , (pdf version) , (ps version)
7. 03/1: Learning decision trees. Weakly learning monotone functions. (tex file) , (pdf version) , (ps version)
8. 03/6: Uniform generation of DNF assignments. (tex file) , (pdf version) , (ps version)
9. 03/8: Uniform generation and approximate counting. (tex file) , (pdf version) , (ps version)
10. 03/13: Random walks. (tex file) , (ps version)
11. 03/15: st-connectivity. Uniform generation via random walks on large Markov chains. Generating random spanning trees. (ps version)
12. 03/20: Generating random spanning trees. Preliminary definitions of conductance. (pdf version) (ps version) (texversion)
13. 03/22: Conductance. Generating random matchings of a graph. (pdf version) (ps version) (texversion)
14. 04/3: Finish generating random matchings of a graph. (pdf version) (ps version) (texversion)
15. 04/5: Mixing time and Eigenvalues. Saving random bits via random walks on expanders. (tex version) , (ps version) , (pdf version)
16. 04/10: Finish saving random bits via random walks on expanders. Begin discussion of pairwise independence. (tex version) , (ps version) , (pdf version)
17. 04/19: Pairwise independence. Use in algorithms. Constructing pairwise independent random bits/numbers. (tex version) , (ps version) , (pdf version)
18. 04/24: Reingold's Algorithm for s-t connectivity in deterministic logspace. (tex version) , (ps version) , (pdf version)
19. 04/26:
20. 05/1:
21. 05/3: PRGs and BPP. PRG's and unpredictability. (tex version) , (ps version) , (pdf version)
22. 05/8: Impossibility of deterministic Byzantine agreement in asynchronous communication model. (guest lecturer: Vinod Vaikuntanathan)
23. 05/10: Possibility of randomized Byzantine agreement in asynchronous communication model. (guest lecturer: Vinod Vaikuntanathan)
24. 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).
25. 05/15: (Nisan-Wigderson).

### Homeworks

1. 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.
2. Problem set 1 Handed out 2/21, due 3/6. Hint for problem 5 , Solutions.
3. Problem set 2. Handed out 3/6, due 3/20.
4. Problem set 3. Handed out 3/20, due 4/10. Hint for problem 1
5. Problem set 4. Handed out 4/10, due 4/24.
6. Problem set 5. Handed out 5/1, due 5/12. (Note -- earlier than usual due date). Hint for problem 5