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

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

- 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"
- 09/17:k-wise independence, linearity of expectation, quicksort. (Chap. 1)
- 09/22:Randomized complexity classes, a monte-carlo Min Cut alg. (Chap. 1.1, 1.5, 2.3, 10.2)
- 09/24:Probabilistic inequalities, Chernoff bounds, begin randomized rounding. (Chap 3.1-3.4, 4.1)
- 09/29:Randomized rounding, probabilistic method & method of conditional expectations. (Chap 4.3, 5.1, 5.6)
- 10/01:MAX-SAT, occupancy problems. (Chap 5.2, 3.1, 3.6)
- 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)
- 10/08:Random walks and cover times. (Chap 6.1, 6.3, 6.4, 6.5)
- 10/13:Resistive networks, rapid mixing. (Chap 6.2)
- 10/15:Pseudorandom generators (guest lecture by Steven Rudich. Notes outside his office).
- 10/20:Expander graphs: random construction, uses, Impagliazzo-Zuckerman amplification result. (Chap 6.7, 6.8).
- 10/22:Expanders and eigenvalues. Intro to approx counting. (Chap 11.1)
- 10/27:Approximating the Permanent. (Chap 11.3)
- 10/29:Number-theoretic algorithms, intro. (Chap 14)
- 11/03:Randomized algorithms for primality testing.
- 11/05: Analysis of local optimization algorithms [Bjarni and Adam]
- 11/10: A randomized linear-time MST algorithm [Mihai and Hal] (These notes fix some typos in the ones handed out in class)
- 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).
- 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.
- 11/19: Randomized online algorithms [Gary and Dan T.]. (Chap 13)
- 11/24: Bartal's Randomized Metric Space Approx and Applications [Jochen and Erlendur]
- 12/01: Online Machine Learning [Avrim]
- 12/03: Quantum Computing [John and Jesse]

Avrim Blum Last modified: Tue Jan 18 15:06:34 EST 2000