550.770
MATH
SCIENCES:
Probabilistic
Method
SPRING
1997
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.