Probabilistic Methods in Combinatorics and Computer Science


Graduate Course in Mathematics and Computer Science
Day and time: Wednesdays, 4:15-6: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!