6.895 Randomness and Computation

Instructor: Ronitt Rubinfeld
Teaching Assistant: Matthew Menke
Time: MW 2:30-4:00
Place: 36-112
3-0-9 H-Level Grad Credit
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

Handouts

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

Some useful pointers: