15-859(M): Randomized Algorithms

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

Course description: 

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

Lecture Notes

1. Sep 13. (AG) Introduction. (PS, PDF)
2. Sep 15. (SC) Complexity classes, Identity checking. (PS, PDF) [MR 7.1, 7.2, 7.4]
3. Sep 20. (SC) Finding perfect matchings randomly. (PS, PDF) [MR 7.3, 12.4]
4. Sep 22. (AG) Lower bounds on randomized algorithms. (PS, PDF) [MR 2.1, 2.2]
5. Sep 27. (AG) Randomized Min Cut and related topics. (unedited PS, PDF) [MR 1.1, 10.2]
6. Sep 29. (AG) Occupancy Problems and Hashing. (unedited PS, PDF) [MR 3.1, 3.6, 8.4].
   • Notes on Strongly 2-universal hash families.
7. Oct 4. (AG) Two-level hashing. Markov and Chebychev. (unedited PS, PDF) [MR 8.5, 3.2 + other stuff]
   • A quick note on the space requirement for the FKS scheme.
8. Oct 6. (SC) Sampling, Medians of Means method and DNF counting. (PS, PDF) [MR 11.1, 11.2 + other stuff]
9. Oct 11. (SC) Chernoff bounds: coin flipping and randomized rounding. (PS, PDF) [MR 4.1 + other stuff]
10. 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.
11. Oct 18. (AG) Randomized Routing, the Probabilistic Method [MR 4.2, 5.3, AS pg.81]
12. Oct 20. (AG) Lovasz Local Lemma (LLL): Packet Routing Schemes [MR 5.5 + other stuff]
    • 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, PDF).
13. Oct 25. (AG) Lipschitz functions, Martingales, and Concentration of Measure. [MR 4.4, AS Ch.7 (2nd ed.)]
14. Oct 27. (AG) Martingales (contd.), concentration of geometric TSP  [AS Ch.7 (2nd ed.)]
    • Some notes on the TSP argument. (PS, PDF)
15. Nov 01. (SC) Random Walks and Electrical Networks  [MR 6.1--6.5]
• The famous book Random Walks and Electric Networks by Doyle and Snell, now available online..
16. Nov 03. (SC) Markov Chains, Rapid Mixing, Conductance  [MR 6.6 + other stuff]
• Jerrum & Sinclair survey on rapid mixing: here.
• Many other surveys/lecture notes on Mark Jerrum's page.
17. Nov 08. (SC) Rapid mixing in Markov Chains: Conductance and Coupling
• Chapter on Coupling by Mark Jerrum.
18. Nov 10. (SC) Examples: Colorings, Matchings, Volume Estimation.
19. Nov 15. (AG) Geometric Algorithms. [MR 9]
• Raimund Seidel's survey on backwards analysis.
• Ken Clarkson's survey on randomness in geometric algorithms.
• Survey by Pankaj Agarwal and Sandeep Sen.
20. Nov 17. (Andrew, Dan G., Nina) Randomized Rounding for Semidefinite Programs.
21. Nov 22. (Ajit, Jon, Runting) Random sampling for undirected s-t mincuts, (Mohit, Vineet, Vishwanath) Algorithmic Aspects of the Lovasz Local Lemma
22. Nov 24. Happy thanksgiving (eve)!
23. Nov 29. (Taka, Anupam) Talagrand's inequality.
24. Dec 1. (Kaustav, Pradeep) Deviation Bounds for Markov Chains, (David O., Pálli) Load Balancing with Memory
25. Dec 6. (Shobha, David, Steven) Property Testing, (Florin), (Dan B.) Cuckoo Hashing
26. Dec 8. (Mugizi, Jeff) Near-neighbor searching, (Sri, Chris)

Homeworks

1. Sep 20. Homework 1. (PS, PDF). (Due Oct 4th.) Solutions
2. Oct 04. Homework 2. (PS, PDF). (Due Oct 18th.) Solutions
3. Oct 18. Homework 3. (PS, PDF). (Due Nov 1st.) Solutions
4. Nov 1. Homework 4. (PS, PDF). (Due Nov 15th in class; no collaboration.) Solutions
5. Nov 15. Homework 5. (PS, PDF). (Due Nov 29th in class, no collaboration.) Solutions

Misc Documents

1. Scribe notes LaTeX template here.
2.  

Last updated: 12/03/2004