15-859(M): Randomized Algorithms
Gupta and Shuchi Chawla
- Time: MW 3:00-4:20, Wean 5409
Office Hours: just send mail. We will hold formal office hours if
there is enough demand.
Randomness has proven itself to be a useful resource for developing
provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore techniques for effectively using randomization and for analyzing randomized algorithms, as well as
examples from a variety of settings and problem areas.
- Sep 13. (AG) Introduction.
- Sep 15. (SC) Complexity classes, Identity checking.
[MR 7.1, 7.2, 7.4]
- Sep 20. (SC) Finding perfect matchings randomly.
- Sep 22. (AG) Lower bounds on randomized algorithms.
[MR 2.1, 2.2]
- Sep 27. (AG) Randomized Min Cut and related topics.
[MR 1.1, 10.2]
- Sep 29. (AG) Occupancy Problems and Hashing. (unedited PS,
PDF) [MR 3.1, 3.6, 8.4].
- Notes on Strongly
2-universal hash families.
- Oct 4. (AG) Two-level hashing. Markov and Chebychev. (unedited PS,
PDF) [MR 8.5, 3.2 + other stuff]
- Oct 6. (SC) Sampling, Medians of Means method and DNF counting.
[MR 11.1, 11.2 + other stuff]
- Oct 11. (SC) Chernoff bounds: coin flipping and randomized rounding.
[MR 4.1 +
- Oct 13. (AG) Balls and bins: the power of two choices (unedited PS,
PDF) [not in MR]
- Berthold Vöcking's presentation
on the power of two choices.
- Oct 18. (AG) Randomized Routing, the Probabilistic Method [MR 4.2, 5.3, AS
- Oct 20. (AG) Lovasz Local Lemma (LLL): Packet Routing Schemes [MR 5.5 +
- The Leighton Maggs Rao paper:
sections 2 and 3.1 are the relevant ones.
- Aravind Srinivasan's
notes on LLL + the Leighton Maggs Rao scheme (PS,
- Oct 25. (AG) Lipschitz functions, Martingales, and Concentration of Measure. [MR
4.4, AS Ch.7 (2nd ed.)]
- Oct 27. (AG) Martingales (contd.), concentration of geometric
TSP [AS Ch.7
- Some notes on the TSP argument. (PS,
- Nov 01. (SC) Random Walks and Electrical Networks [MR 6.1--6.5]
Nov 03. (SC) Markov Chains, Rapid Mixing, Conductance [MR 6.6 + other stuff]
- The famous book
Random Walks and Electric Networks by Doyle and Snell, now
Nov 08. (SC) Rapid mixing in Markov Chains: Conductance and
- Jerrum & Sinclair survey on rapid mixing: here.
- Many other surveys/lecture notes on Mark Jerrum's page.
Nov 10. (SC) Examples: Colorings, Matchings, Volume
Nov 15. (AG) Geometric Algorithms. [MR 9]
Chapter on Coupling by Mark Jerrum.
Nov 17. (Andrew, Dan G., Nina) Randomized Rounding for Semidefinite
Nov 22. (Ajit, Jon, Runting) Random sampling for undirected s-t
mincuts, (Mohit, Vineet, Vishwanath) Algorithmic Aspects of the
Lovasz Local Lemma
Nov 24. Happy thanksgiving (eve)!
Nov 29. (Taka, Anupam) Talagrand's inequality.
Dec 1. (Kaustav, Pradeep) Deviation Bounds for Markov Chains, (David O., Pálli)
Load Balancing with Memory
Dec 6. (Shobha, David, Steven) Property Testing, (Florin), (Dan B.) Cuckoo
Dec 8. (Mugizi, Jeff) Near-neighbor searching, (Sri, Chris)
- Raimund Seidel's survey
on backwards analysis.
- Ken Clarkson's survey
on randomness in geometric algorithms.
by Pankaj Agarwal and Sandeep Sen.
(Solutions accessible only from within CMU.)
- Sep 20. Homework 1.
(Due Oct 4th.) Solutions
- Oct 04. Homework 2.
(Due Oct 18th.) Solutions
- Oct 18. Homework 3. (PS, PDF). (Due Nov
- Nov 1. Homework 4. (PS, PDF).
(Due Nov 15th in class; no collaboration.) Solutions
- Nov 15. Homework 5. (PS, PDF). (Due Nov 29th in class, no collaboration.) Solutions
- Scribe notes LaTeX template here.
Last updated: 12/03/2004