Randomized algorithms

Algorithms that use randomness are often faster, easier to implement and easier to understand than deterministic algorithms, and in some cases, the only efficient algorithm we know for solving a problem is a randomized one. Understanding the role that randomness plays in computation is one of the great scientific questions of our time. This course will survey various algorithmic techniques, covering different aspects of the use of randomness in computation.

Possible topics include (but are not limited to): random sampling, random walks, randomized data structures, random graph models, minimum spanning trees and cuts in graphs, randomized verification, predicting the future with the help of experts, geometric algorithms, randomized incremental construction, load balancing, pattern matching, the probabilistic method, Chernoff bounds, primality testing, isolation, ski-rental and paging, approximation and LP-rounding.

(The course will be given in English.)