CSE 525: Randomized Algorithms and Probabilistic Analysis (WI 11)

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

important announcements

course description

Instructor: Anna Karlin, CSE 594, tel. 543 9344
Time: Mondays and Wednesdays in EEB 031, 12-1:20pm
Office hours:  By appointment -- send email.

Teaching assistant: Punyashloka Biswal
Office hours:

Course evaluation: Homework and a final exam.

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

Required (or at least highly recommended) text:
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.

Courses at other schools:

Suggested references:

lectures

Key (see references above):
  1. January 3: Overview, fingerprinting ([MR] Section 7.4, [CG] Section 2.2.1), MAX-CUT ([MU] Section 6.2.1, [CG] Section 1.4.1).
  2. January 5: Matrix-product verification [MU 1.3], [MR 7.1], Min-cut [MU 1.4], [CG Lecture 5].
  3. January 10: Coupon-collectors [MU 2.4], Markov and Chevychev Inequalities [MU 3.1-3.3], Poisson approximation (some of [MU 5.3-5.4])
  4. January 19: Backwards analysis -- 2D convex hull [Seidel survey, Section 4]
  5. January 24: Chernoff bounds and applications [MU, Chapter 4, MR 4.1]. Here are the slides. The main application was randomized rounding analysis to approximately solve the integer multicommodity flow problem. [B Lecture 7].
  6. January 26: Randomized rounding of SDPs: Goemans Williamson MAX-CUT algorithm.
  7. January 31: Permutation routing on the hypercube [MU Section 4.5.1, MR Section 4.2]
  8. February 2: Universal hashing and perfect hashing [MU Section 13.3, MR Sections 8.4-8.5]
  9. February 7: Markov Chains [MU Chapter 7, MR Sections 6.1-6.3, 6.6]
  10. February 9: Markov Chains continued.
  11. February 14: Random walks and electrical networks [MR, Section 6.4, B Lectures 8-9, Lecture notes here and here.]
  12. February 16: Rapidly mixing random walks and expansion [MR, Section 6.7 and these lecture notes: Section 3 here, Section 1 here, first part of these, and these. Additional material can be found in the rest of lectures 8-11 in these lecture notes by Luca Trevisan. For details on an explicit construction of expanders, see these notes. Here is another great reference on expanders].
  13. February 23: Probability amplification by random walks on expanders [MR 6.8]
  14. February 28: Monte Carlo Methods [MU Chapter 10]
  15. March 2: Markov Chain Monte Carlo [MU Section 10.4, this survey and references therein], coupling [MU Sections 11.1-11.2]
  16. March 7: Martingales [MU, Chapter 12]
  17. March 9: Review of what we did and didn't do.

assignments

  1. Homework #1 due Wednesday, January 19.
  2. Homework #2 due Wednesday, February 2.
  3. Homework #3 due Wednesday, February 16.
  4. Homework #4 due Wednesday, March 2.
  5. Homework #5 due Friday, March 11 at 1pm.