Probabilistic Method

Instructor: Lenore Cowen,

This is a seminar course that I taught in Spring 1995 and Fall 1997. The lecture notes below come from both versions of the class. The course included material on the basic Erdos-Spencer probabilistic method, a bit on Random Graphs, and a bit on removing randomness from parallel algorithms. You are welcome to use these notes for your class, I only ask that you reference this page.

Primary Text: Spencer, J., Ten Lectures in the Probabilistic Method.

Scribe notes:

  • Lecture 1 (Basic examples of the method: Ramsey numbers, tournaments, etc)
  • Lecture 2 (Deletion method and other refinements)
  • Lecture 3 (Tails of distributions, Chebechev's etc)
  • Lecture 4 (Lovasz Local Lemma)
  • Lecture 5 (Constructing small sample spaces, method of pessimistic estimators)
  • Lecture 6 (Parallel algorithm for MIS)
  • Lecture 7 (Low diameter network decomposition)
  • Lecture 8 (From Pairwise to 3-wise independence)
  • Lecture 9 Guest Lecture by Mike Goodrich (Geometric Partitioning)
  • Lecture 10 (Set discrepancy)
  • Lecture 11 (Algorithmic Aspects of the Local Lemma)
  • Lecture 12 (Janson's Inequalities)
  • Lecture 13 (Random Graphs I)
  • Lecture 14 (Random Graphs II)
  • Lecture 15 (Matching Nuts and Bolts I)
  • Lecture 16 (Matching Nuts and Bolts II)

    Partial Bibliography.