Randomized Algorithms and Probabilistic Analysis

CSE 525: Randomized Algorithms and Probabilistic Analysis (Spring 2013)

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

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

lectures

Key (see references below):

[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

Scribe notes have NOT been vetted.

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].
- Scribe notes, Anna's notes
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]
- Scribe notes
- Anna's notes
April 18: Universal hashing and perfect hashing [MU Section 13.3, MR Sections 8.4-8.5]

Scribe notes

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]
- Anna's notes
- Scribe notes
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]
- Anna's notes
- Scribe notes
June 4: Coupling, martingales [MU Sections 11.1-11.2, Chapter 12][LPW Chapter 17]
- Anna's notes
- Scribe notes
June 6: Finish discussion of martingales, Lovett/Meka algorithm for discrepancy

assignments

course description

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.

related material

Recommended text:
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.

Courses at other schools:

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.