CSE 525: Randomized Algorithms and Probabilistic Analysis (Spring 2013)
| related material]
| important announcements]
Key (see references below):
Scribe notes have NOT been vetted.
- [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).
- April 4:
Method of conditional expectation [V pp 39-42], Min-cut [MU 1.4], [CG Lecture 5].
- 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
[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
- Suggested reading: [B] Lecture 7
- April 25: online bipartite matching
- April 30: online bipartite matching continued + intro SDP
- May 2: SDP rounding: Max-Cut and Graph coloring
- 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]
- May 23: Random walks and electrical networks [LPW Chap 9, 10.1-10.3, MR, Section 6.4, B Lectures 8-9]
- May 28: Laplacian, electrical networks and their applications [LPW Chap 9, 10.1-10.3, MR, Section 6.4, B Lectures 8-9]
- May 30: Monte Carlo Methods [MU Chapter 10,
this survey and references
- 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
- 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.
and Computing: Randomized Algorithms and Probabilistic Analysis
by Michael Mitzenmacher and Eli Upfal.
Courses at other schools: