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

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

Lecture Notes, Readings, etc.

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)
   * Avrim's notes from the previous incarnation of the course.
   * Discussion on derandomization, and references on our blog
   * The Goemans-Williamson paper giving the 3/4 approximation.
7. 01/31: The Lovasz Local Lemma. (Chap 5.5)
   * The Leighton Maggs Rao paper giving the O(C+D)O(C+D)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)
   * Notes and references on the blog, or as a PDF.
   * Copy of notes from Mitzenmacher and Upfal (CMU/Pitt only).
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.
    * Notes and references on the blog, or as a PDF.
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

1. 02/21: Learning Theory II: online learning.

• Learning from expert advice, Randomized Weighted Majority, the Bandit problem and Exp3 algorithm

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

1. 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.
2. 03/02: FRT/Bartal distance-preserving trees: II.
   * Notes (continued).
   * Combined notes as a PDF.
   03/07: no class (spring break)
   03/09: no class (spring break)
3. 03/14: The Johnson-Lindenstrauss Flattening Lemma.
   * Notes on the blog and in PDF.
   * plus, an alternative view of the second moment sketch (PDF).
4. 03/16: Oblivious routing on a hypercube (Valiant/Valiant-Brebner) (Chap 4.2).
   * Plus a very brief intro to Martingales (Chap 4.4)

• See also excellent notes of Satish Rao: notes 1, notes 2

1. 03/21: More martingales.
   * Notes on the blog and in PDF.
2. 03/23: Learning Theory III: Rademacher bounds.
3. 03/28: Random walks and cover times, resistive networks. (Chap 6.1, 6.3, 6.4, 6.5)
4. 03/30: Rapid mixing, Expander graphs, Impagliazzo-Zuckerman amplification result. (Chap 6.2, 6.7, 6.8).
5. 04/04: Expanders and eigenvalues. Also added node by Noga Alon. (Chap 11.1)
6. 04/06: Rapid mixing for approximate counting and approximating the permanent. (Chap 11.2, 11.3)
7. 04/11: Random rounding of Semi-definite Programs (SDPs)
   * Notes on max-cut rounding (from a previous course, lecture by Ryan).
   * His lecture on coloring 3-colorable graphs gives an improved bound we didn't get to.
   * Chapter 6 of the Williamson/Shmoys book has very nice notes; more advanced stuff is in Chapter 13.
8. 04/13: Randomization in Computational Geometry. (Chap 9)
   * Notes on backwards analysis by Raimund Seidel.

• The crossing number lemma.

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

1. 04/20: Differential privacy.
2. 04/25: Quantum computing
3. 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