**[course description**
| **lectures**
| **assignments**
| **related material]**
| **important announcements]**

- Scribe notes:
- Here is the latex template you should use for your scribe notes. Here is a sample latex file and the resulting sample pdf. You will also need this preamble file.
- Notes are due one week after the class.
- Current scribe schedule

- [MU] -- Mitzenmacher/Upfal
- [MR] -- Motwani/Raghavan
- [AS] -- Alon/Spencer
- [CG] -- Gupta/Chawla lecture notes
- [B] -- Avrim Blum lecture notes
- [V] -- Vadhan monograph
- [HP] -- Sariel Har-Peled lecture notes
- [DP] -- Dubhashi/Panconesi
- [WS] -- Williamson/Shmoys
- [LPM] -- Levin/Peres/Wilmer

- April 2: Overview, Matrix-product verification [MU 1.3], [MR 7.1], fingerprinting ([MR] Section 7.4,
[CG] Section 2.2.1), MAX-CUT ([MU] Section 6.2.1, [CG] Section 1.4.1).
- Scribe notes, Anna's notes
- Recommended reading: [MU] Chapters 1-3.

- April 4:
Method of conditional expectation [V pp 39-42], Min-cut [MU 1.4], [CG Lecture 5].
- Scribe notes, Anna's notes
- Recommended reading: these notes by Jeff Erickson, and of course the original paper

- April 9: Markov and Chevychev Inequalities [MU 3.1-3.3], Chernoff bounds [MU, Chapter 4, MR 4.1], [DP, Chapter 1], [WS, 5.10].
- April 11: Randomized rounding: Set Cover and MAX-SAT [O'Donnell Notes] [B Lecture 7], [WS Sections 1.2, 1.7, 5.4, 5.6]
- April 18: Universal hashing and perfect hashing [MU Section 13.3, MR Sections 8.4-8.5]
- April 23: randomized rounding: integer multicommodity flow
- Scribe notes
- Anna's notes on integer multicommodity flow at end of this
- Suggested reading: [B] Lecture 7
- April 25: online bipartite matching
- Scribe notes
- Anna's notes
- Randomized primal-dual analysis for online bipartite matching, by Devanur, Jain and Kleinberg.
- April 30: online bipartite matching continued + intro SDP
- May 2: SDP rounding: Max-Cut and Graph coloring
- Scribe notes
- Anna's notes: Max-Cut and Coloring
- Max-Cut paper by Goemans and Williamson
- Coloring paper by Karger, Motwani and Sudan.
- May 7: Probabilistic Method, 2nd moment method [MU 6.5][AS Chap 4,10.7]
- May 9: Lovasz Local Lemma [MU 6.7]
- May 14: Lovasz Local Lemma Constructive Version
- May 16: Markov chains and random walk based bipartite matching algorithm [MU Chapter 7, MR Sections 6.1-6.3, 6.6, LPW Chapter 1, 4.3]
- May 21: Random walks [MU Chapter 7, MR Sections 6.1-6.3, 6.5-6.7]
- Anna's notes
- Scribe notes (incomplete).
- Luca Trevisan notes: review of linear algebra and expansion and second eigenvalue computations

- May 23: Random walks and electrical networks [LPW Chap 9, 10.1-10.3, MR, Section 6.4, B Lectures 8-9]
- Anna's notes
- Scribe notes
- Doyle and Snell's classical account
- Other lecture notes here and here.

- May 28: Laplacian, electrical networks and their applications [LPW Chap 9, 10.1-10.3, MR, Section 6.4, B Lectures 8-9]
- Anna's notes
- Scribe notes
- Breakthrough papers on maxflow here and here
- Spectral sparsification here and here
- Lecture notes on spectral graph theory by Dan Spielman here and by Jonathan Kelner here
- Solving SDD systems in near linear time

- May 30: Monte Carlo Methods [MU Chapter 10, this survey and references therein]
- June 4: Coupling, martingales [MU Sections 11.1-11.2, Chapter 12][LPW Chapter 17]
- June 6: Finish discussion of martingales, Lovett/Meka algorithm for discrepancy

**Instructor:** Anna Karlin,
CSE 594, tel. 543 9344

Time: Tuesdays and Thursdays
in MGH 234, 10:30-11:50pm

**Office hours:** By appointment -- send email.

**Teaching assistant:** Paris Koutris

**Office hours:**

- Tuesdays, 5-6pm, in CSE 306.
- Also by appointment -- send email.

**Course evaluation: **homework (~35%), scribe notes (~35%), and a final exam (~30%).

**About this course:**

Randomization and probabilistic analysis have become fundamental tools
in modern Computer Science,
with applications ranging from combinatorial optimization to machine
learning to cryptography to
complexity theory to the design of protocols for communication
networks. Often randomized algorithms
are more efficient, and conceptually simpler and more elegant than
their deterministic counterparts.

We will cover some of the most widely used techniques for the analysis of randomized algorithms and the behavior of random structures from a rigorous theoretical perspective. A (non-random) sample of topics to be covered includes elementary examples like fingerprinting and minimum cut, large-deviation inequalities, the probabilistic method, martingales, random graphs, and the analysis of Markov chains. Tools from discrete probability will be illustrated via their application to problems like randomized rounding, hashing of high-dimensional data, and load balancing in distributed systems.

**Courses at other schools:
**

- Lecture notes by Lap Chi Lau at Chinese University of Hong Kong.
- Lecture notes by Nick Harvey at UBC
- Lecture notes by Avrim Blum at CMU.
- Lecture notes by Anupam Gupta and Shuchi Chawla at CMU.
- Lecture notes by Sariel Har-Peled at UIUC.

**Suggested references:**

*Randomized Algorithms*by Motwani and Raghavan.*Concentration of Measure for the Analysis of Randomized Algorithms*by Dubhashi and Panconesi.*The Probabilistic Method*by Alon and Spencer.*Markov Chains and Mixing Times*by Levin, Peres and Wilmer.*Probability and Random Processes*(2nd ed.) by Grimmett and Stirzaker.*Approximation Algorithms*, by David Williamson and David Shmoys- Pseudorandomness by Salil Vadhan.
- Here are some slides by Eli Upfal for the more basic material.