
Graduate Course in Mathematics and Computer Science
Day and time: Wednesdays, 4:156:15 p.m.
Place: CUNY Graduate Center, 365 Fifth Avenue
Offered by János Pach
Spring Term, 2001



The exciting fact that randomness (i.e., coin flipping)
can be used profitably to construct various mathematical structures with
unexpected and often paradoxical properties, and to efficiently solve
many { otherwise hopelessly difficult { computational tasks, attracted
a lot of interest during the past 25 years. In this course, we give a
systematic introduction to the most important applications of this idea.
No special knowledge of combinatorics is required. However, we assume
some familiarity with the basic notions of probability theory (expectation
and variance of random variables, binomial distribution).
Topics:
 Linearity of expectation
 Applications in combinatorics and number theory
 Randomized algorithms (sorting, convex hull,
linear programming)
 The second moment method
 Random graphs
 Circuit complexity
Textbook: N.
Alon and J. Spencer: The Probabilistic Method (2nd edition), J. Wiley
and Sons, New York, 2000.
Bonus lecture: The course will include
a guest appearance by at least one of the authors!

