## 15-859(D) RANDOMIZED ALGORITHMS

Instructor: Avrim Blum
Time: TR 10:30-11:50
Place: Wean 5409B
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: Monday 10:30-12:00, or by appointment.

Here is the Take-home Final. Due Friday Dec 11, 4:00pm.

### 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]

Avrim Blum