CSIS8601 Advanced Topics in Theoretical Computer Science:
Probabilistic Method & Randomized Algorithms, Fall 2009

Instructor: Hubert Chan
TA: Simon Zhang
Time: Wed 2:00-4:05pm
Place: Theatre B, Chow Yei Ching Building

Instructor's Office Hours: after each class
TA Consultation Hours: Friday 4-6pm

Course description: 

This is a graduate level course that covers probability techniques in the design and the analysis of randomized algorithms. Topics include measure concentration results such as Chernoff Bound, Hoeffding's Inequality and martingale inequalities. We also cover classical results such as the Johnson-Lindenstrauss Lemma and the Lovasz Local Lemma. This course puts emphasis on understanding how the various techniques work. However, we would explain the proofs from the computer scientist's viewpoint and avoid the pedantic axiomatic approach.

Prerequisites:Students should have a basic knowledge of probability and algorithms. For example, probability space, discrete and continuous random variables, expectation, independence, probability density function, normal (Gaussian) distribution. However, we would also recall the necessary concepts as the course proceeds.

Method of Assessment: There will be 4 or 5 homeworks (25%), a mid-term exam (25%) and a final exam (50%).

Textbook: There is no compulsory text, but here are some suggested textbooks:

Tentative List of Topics

The list of topics is subject to change according to the pace and interests of students.
  • Markov's inequality, Chebyshev's inequality, probabilistic method
  • Chernoff Bound
  • Approximate Sampling and Counting
  • Dimension reduction, Johnson-Lindenstrauss Lemma
  • Lovasz Local Lemma
  • VC dimension, epsilon nets, epsilon samples

    • Lecture Slides and Notes

    1. 2 Sep. Course info, basics of probability, probabilistic method.
      • Slides. (Course admin, Probability basics)
      • Notes. (Probabilistic Method, Markov's Inequality, Chebyshev's Inequality)
    2. 9 Sep. Derandomization by Conditional Expectation, Graphs with No Short Cycles (Method of Alteration)
    3. 16 Sep. Chernoff Bound, Measure Concentration
    4. 23 Sep. More Measure Concentration: Counting DNF Satisfying Assignments, Hoeffding's Inequality.
    5. 30 Sep. Johnson-Lindenstrauss Lemma: Dimension Reduction
    6. 7 Oct. Locality Sensitive Hashing: Nearest Neighbor Search
      • Notes.
      • 14 Oct. Reading Week. No Class
      • 21 Oct. Midterm
      • 28 Oct. Review of Materials from midterm, homework, past lectures.
    7. 4 Nov. epsilon-Nets, VC-Dimension
    8. 11 Nov. epsilon-Nets, epsilon-Samples, VC-Dimension (Part 2)
    9. 18 Nov. Lovasz Local Lemma, Job Shop Scheduling.
    10. 25 Nov. Lovasz Local Lemma (Part 2): Asymptotically Optimal Job Shop Scheduling

    Homeworks

    1. Homework 1, due 16 Sep.
    2. Homework 2, due 7 Oct.
    3. Homeworks 3+4, due 25 Nov.