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
(Solutions accessible only from within CMU/Pitt.)
- Homework 1. Due Jan 26. Solutions.
- Homework 2. Due Feb 9. Solutions.
- Homework 3. Due Feb 23. Solutions.
- Homework 4. Due Mar 16. Solutions.
- Homework 5. Due Apr 4. Solutions (partial).
- Homework 6. Due Apr 27.
- Final. Due 48 hours after you start, Friday 5/6 11:59pm at the latest.
Lecture Notes, Readings, etc.
- 01/10: Admin, Intro, Example:
3-colorable graph. "If you can't walk
in the right direction, sometimes it's enough to walk randomly";
- 01/12: Basic definitions, linearity of
expectation, quicksort, game theoretic view, randomized
lower bounds. (Chap. 1, 2.2)
- 01/17: no class (MLK day)
- 01/19: Randomized complexity classes, a
monte-carlo Min Cut alg. (Chap. 1.1, 1.5, 2.3, 10.2)
- 01/24: Probabilistic inequalities: Markov,
Chebyshev, Chernoff bounds, randomized rounding. (Chap
3.1-3.4, 4.1, 4.3)
- 01/26: MAX-SAT, probabilistic
method & method of conditional expectations. (Chap
5.1, 5.2, 5.6)
- 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.
- 02/02: Balls and bins and the power of 2 choices.
(Chap 3.1, 3.6)
- 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.
- 02/09: Polynomial Identity testing and finding matchings in parallel.
- 02/14: Online Algorithms:
elevators, ski-rental, and paging.
- 02/16: Learning Theory I:
learning from iid data.
- The PAC model, Occam's razor,
shatter coefficients / VC-dimension, ghost-sample arguments
- 02/21: Learning Theory II:
- Learning from expert advice,
Randomized Weighted Majority, the Bandit problem and
- 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.
- 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.
- 03/02: FRT/Bartal distance-preserving trees: II.
03/07: no class (spring break)
03/09: no class (spring break)
- 03/14: The Johnson-Lindenstrauss Flattening Lemma.
- 03/16: Oblivious routing on a
hypercube (Valiant/Valiant-Brebner) (Chap 4.2).
- 03/21: More martingales.
- 03/23: Learning Theory III: Rademacher bounds.
- 03/28: Random walks and cover
times, resistive networks. (Chap 6.1, 6.3, 6.4, 6.5)
- 03/30: Rapid mixing, Expander graphs,
Impagliazzo-Zuckerman amplification result. (Chap 6.2, 6.7, 6.8).
- 04/04: Expanders and
eigenvalues. Also added node by Noga
Alon. (Chap 11.1)
- 04/06: Rapid mixing for approximate counting and approximating the permanent. (Chap 11.2, 11.3)
- 04/11: Random rounding of Semi-definite Programs (SDPs)
- 04/13: Randomization in Computational Geometry. (Chap 9)
- 04/18: Graph Sparsification.
- Karger's paper showing that sampling preserves cuts when min-cuts are large. (Theorem 2.1)
- The Benczur-Karger paper with general graph sparsification.
- Recent developments mentioned in lecture: Spielman & Srivastava, Batson, Spielman & Srivastava, and
Fung, Harvey, Hariharan & Panigrahi (merged stoc '11 paper).
- Not covered/mentioned in lecture: sparsification in streaming models Kelner-Levin, Goel, Kapralov, Khanna, Ahn, Guha, etc.
- 04/20: Differential privacy.
- 04/25: Quantum computing
- 04/27: project presentations and pizza party Schedule.
- Ipe: a simple yet powerful drawing editor.
- 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