Instructor: Avrim Blum
Time: MW 10:30-11:50
Place: Wean 4615A
12 Units, 1 CU
Course description: Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore a collection of techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas.

Text: Randomized Algorithms by Rajeev Motani and Prabhakar Raghavan, plus papers and notes for topics not in the book.

Office hours: Friday 10:30-12:00


Lecture Notes

  1. 01/13:Admin, Intro, Example: partitioning a 3-colorable graph. "If you can't walk in the right direction, sometimes it's enough to walk randomly"
  2. 01/15:Secretly computing an average, k-wise independence, linearity of expectation, quicksort. (Chap. 1)
  3. 01/20:probabilistic inequalities, Chernoff bounds, complexity classes. (Chap. 2.3, 3.1-3.4, 4.1)
  4. 01/22:A monte-carlo Minimum Cut algorithm. (Chap. 1.1, 10.2)
  5. 01/27:Universal and perfect hashing. (Chap. 8.4, 8.5)
  6. 01/29:Balls'n'boxes, lower bounds, Spencer's graduation game. (Chap 2.2.2, 3.1, 3.6, 5.1)
  7. 02/03:Randomized rounding, probabilistic method. (Chap 4.3, 5.1, 5.2, 5.6)
  8. 02/05:Random walks and cover times. (Chap 6.1, 6.3, 6.4, 6.5)
  9. 02/10:Resistive networks, existence of expanders. (Chap 5.3, 6.2)
  10. 02/12:Amplifying randomness via random walks on expanders. (Chap 6.7, 6.8)
  11. 02/17:Expanders, eigenvalues, and rapid mixing. Randomized Clique hardness reduction.
  12. 02/19:Expanders&eigenvalues, intro to approx counting | Noga's quick proof. (Chap 11.1)
  13. 02/24:Approximating the Permanent, part 1.(Chap 11.3)
  14. 02/26:Approximation the Permanent, part 2.
  15. 03/05:[Rachel Rue] An approximation scheme for Euclidean TSP. (See Rachel for slides)
  16. 03/10:Analysis of local optimization algorithms. From Aldous-Vazirani and Dimitriou-Impagliazzo
  17. 03/12:[Goran Konjevod] Explicit construction of expanders. (See Goran for slides)
  18. 03/17:Intro to number-theoretic algorithms. (Chap 14)
  19. 03/19:Randomized algorithms for primality testing.
  20. 03/31:[Adam Kalai] Byzantine agreement. (Chap 12.6)
  21. 04/02:[Nate Segerlind] PCP and approximability, begin NP in PCP(poly,1). (Chap 7.1, 7.8)
  22. 04/07:Finish NP in PCP(poly,1). (Here are some old notes of mine).
  23. 04/09:[Ion Stoica] The Choice Coordination Problem. (Chap 12.5)
  24. 04/14:[Carl Burch] A randomized linear-time MST algorithm (Chap 10.3)
  25. 04/16:[Mike Harkavy] Pseudorandom number generators based on hardness of factoring.
  26. 04/21:[Mark Moll] Randomized linear programming algorithms. (Chap 9.10)
  27. 04/23:Randomized algorithms for on-line problems. (Chap 13.1, 13.3)
  28. 04/28: Quantum computation, Shor's factoring algorithm. Slides available outside Wean 4116.
  29. 04/30:[Leemon Baird] Thermal ensembles, quantum cryptography, and a really weird algorithm. Slides available outside Wean 4116.