|
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!
|
|