15-859(D) RANDOMIZED ALGORITHMS

Instructor: Avrim Blum

Time: TR 10:30-11:50

Place: Wean 5409B

12 Units, 1 CU

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

Office hours: Monday 10:30-12:00, or by appointment.

Handouts

• General Course Information
• Homework 1. Due September 29. Solutions.
• Homework 2. Due October 8. Solutions. FYI, Here is a paper by Edith Cohen that this assignment was based on.
• Homework 3. Due October 20. Solutions.
• Homework 4. Due October 29. Solutions.
• Homework 5. Due November 19. Solutions.
• Homework 6. Due December 3.
  Clarification: to calculate OPT, you can either assume OPT starts at LEFT or assume OPT gets to pick its own starting point. If we assume OPT starts at LEFT, and if d=10 and we get cost vectors (5,3) and (100,2), then OPT_r = 15 and OPT_l = 25; (optimal way to end at left is to move right initially, do all the tasks, and then move back)
• Papers:
  • Noga Alon's paper on Expanders and Eigenvalues.
  • Noga Alon's email note.
  • On the theory of computing symposia.
  • Jerrum and Sinclair: Approximating the Permanent.

Lecture Notes

1. 09/15: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. 09/17:k-wise independence, linearity of expectation, quicksort. (Chap. 1)
3. 09/22:Randomized complexity classes, a monte-carlo Min Cut alg. (Chap. 1.1, 1.5, 2.3, 10.2)
4. 09/24:Probabilistic inequalities, Chernoff bounds, begin randomized rounding. (Chap 3.1-3.4, 4.1)
5. 09/29:Randomized rounding, probabilistic method & method of conditional expectations. (Chap 4.3, 5.1, 5.6)
6. 10/01:MAX-SAT, occupancy problems. (Chap 5.2, 3.1, 3.6)
7. 10/06:Universal and perfect hashing, randomized lower bounds. Slides for 1st half, Notes for second half. (Chap 8.4, 8.5, 2.2.2)
8. 10/08:Random walks and cover times. (Chap 6.1, 6.3, 6.4, 6.5)
9. 10/13:Resistive networks, rapid mixing. (Chap 6.2)
10. 10/15:Pseudorandom generators (guest lecture by Steven Rudich. Notes outside his office).
11. 10/20:Expander graphs: random construction, uses, Impagliazzo-Zuckerman amplification result. (Chap 6.7, 6.8).
12. 10/22:Expanders and eigenvalues. Intro to approx counting. (Chap 11.1)
13. 10/27:Approximating the Permanent. (Chap 11.3)
14. 10/29:Number-theoretic algorithms, intro. (Chap 14)
15. 11/03:Randomized algorithms for primality testing.
16. 11/05: Analysis of local optimization algorithms [Bjarni and Adam]
17. 11/10: A randomized linear-time MST algorithm [Mihai and Hal] (These notes fix some typos in the ones handed out in class)
18. 11/12: Lovasz local lemma, Janson's inequality, and Talagrand's inequality [Shyjan and Geoff and Shelby]. Joel Spencer's notes on Talagrand's inequality, and his Ohio State Lectures (which discuss LLL and Janson's, among other things).
19. 11/17: Rounding an SDP [Dan P and Larry and Avrim]. Here are Dan Pelleg's slides (click on "swap landscape" in ghostview). Here is the Karger-Motwani-Sudan paper.
20. 11/19: Randomized online algorithms [Gary and Dan T.]. (Chap 13)
21. 11/24: Bartal's Randomized Metric Space Approx and Applications [Jochen and Erlendur]
22. 12/01: Online Machine Learning [Avrim]
23. 12/03: Quantum Computing [John and Jesse]