- 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

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

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

- 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.
- 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)
- Notes and references on the blog, or as a PDF.
- Copy of notes from Mitzenmacher and Upfal (CMU/Pitt only).

- 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.
- Notes and references on the blog, or as a PDF.

- 02/14: Online Algorithms: elevators, ski-rental, and paging. (Chap 13)
- 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:
online learning.
*Learning from expert advice, Randomized Weighted Majority, the Bandit problem and Exp3 algorithm*

- 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.
- Notes (continued).
- Combined notes as a PDF.

03/09: no class (spring break) - 03/14: The Johnson-Lindenstrauss Flattening Lemma.
- Notes on the blog and in PDF.
- plus, an alternative view of the second moment sketch (PDF).

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

- 03/21: More martingales.
- Notes on the blog and in PDF.

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

- 04/13: Randomization in Computational Geometry. (Chap 9)
- Notes on backwards analysis by Raimund Seidel.
*The crossing number lemma.*

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