## 15-859(M): Randomized Algorithms, Spring 2011

Avrim Blum and Anupam Gupta
Time: MW 1:30-2:50, GHC 4102
Course blog: http://cmurandomized.wordpress.com/

Office Hours: TBA
Course description: policies etc. here

### Homeworks

1. Homework 1. Due Jan 26. Solutions.
2. Homework 2. Due Feb 9. Solutions.
3. Homework 3. Due Feb 23. Solutions.
4. Homework 4. Due Mar 16. Solutions.
5. Homework 5. Due Apr 4. Solutions (partial).
6. Homework 6. Due Apr 27.
7. Final. Due 48 hours after you start, Friday 5/6 11:59pm at the latest.
(Solutions accessible only from within CMU/Pitt.)

1. 01/10: Admin, Intro, Example: partitioning a 3-colorable graph. "If you can't walk in the right direction, sometimes it's enough to walk randomly"; Schoning's algorithm
2. 01/12: Basic definitions, linearity of expectation, quicksort, game theoretic view, randomized lower bounds. (Chap. 1, 2.2)
3. 01/17: no class (MLK day)
4. 01/19: Randomized complexity classes, a monte-carlo Min Cut alg. (Chap. 1.1, 1.5, 2.3, 10.2)
5. 01/24: Probabilistic inequalities: Markov, Chebyshev, Chernoff bounds, randomized rounding. (Chap 3.1-3.4, 4.1, 4.3)
6. 01/26: MAX-SAT, probabilistic method & method of conditional expectations. (Chap 5.1, 5.2, 5.6)
7. 01/31: The Lovasz Local Lemma. (Chap 5.5)
• The Leighton Maggs Rao paper giving the \$O(C+D)\$ length schedule.
• Aravind Srinivasan's notes on the LLL and the Leighton Maggs Rao paper.
• Terry Tao's notes on the algorithmic LLL specialized to the Ek-SAT result.
• And if you'd like to see the proof of slightly more general versions:
• Notes by Joel Spencer and Uri Feige on the algorithmic versions of LLL.
8. 02/02: Balls and bins and the power of 2 choices. (Chap 3.1, 3.6)
9. 02/07: Cuckoo hashing (guest lecturer: Rasmus Pagh).
• Rasmus's notes, and the original paper of Pagh and Rodler.
• Mike Mitzenmacher's open problems on cuckoo hashing.
Some of the problems in the list have been studied subsequently, so make sure you search online before working on them.
10. 02/09: Polynomial Identity testing and finding matchings in parallel.
11. 02/14: Online Algorithms: elevators, ski-rental, and paging. (Chap 13)
12. 02/16: Learning Theory I: learning from iid data.
• The PAC model, Occam's razor, shatter coefficients / VC-dimension, ghost-sample arguments
13. 02/21: Learning Theory II: online learning.
• Learning from expert advice, Randomized Weighted Majority, the Bandit problem and Exp3 algorithm
14. 02/23: Game Theory.
• Zero-sum games, minimax theorem, connections to experts problem.
• General-sum games and Nash equilibria (and proof of existence).
• Correlated equilibria and connections to swap-regret. See this book chapter.
15. 02/28: The swap-regret algorithm. FRT/Bartal distance-preserving trees.
• Swap-regret results in Section 4.5 of above book chapter
• Notes on distance-preserving trees on the blog.
16. 03/02: FRT/Bartal distance-preserving trees: II.
03/07: no class (spring break)
03/09: no class (spring break)
17. 03/14: The Johnson-Lindenstrauss Flattening Lemma.
18. 03/16: Oblivious routing on a hypercube (Valiant/Valiant-Brebner) (Chap 4.2).
19. 03/21: More martingales.
20. 03/23: Learning Theory III: Rademacher bounds.
21. 03/28: Random walks and cover times, resistive networks. (Chap 6.1, 6.3, 6.4, 6.5)
22. 03/30: Rapid mixing, Expander graphs, Impagliazzo-Zuckerman amplification result. (Chap 6.2, 6.7, 6.8).
23. 04/04: Expanders and eigenvalues. Also added node by Noga Alon. (Chap 11.1)
24. 04/06: Rapid mixing for approximate counting and approximating the permanent. (Chap 11.2, 11.3)
25. 04/11: Random rounding of Semi-definite Programs (SDPs)
26. 04/13: Randomization in Computational Geometry. (Chap 9)
27. 04/18: Graph Sparsification.
28. 04/20: Differential privacy.
29. 04/25: Quantum computing
30. 04/27: project presentations and pizza party Schedule.

### Other Information

1. Ipe: a simple yet powerful drawing editor.
2. A PDF version of Mathematical Writing by Knuth, Larrabee, and Roberts. Please review pp.1-6 before you begin writing solutions/notes/any mathematical content!

Maintained by Avrim Blum and Anupam Gupta