Randomized algorithms
The word "random" often has negative connotations: if something is random, then it may be unpredictable, unprecise, noisy, erratic, difficult to understand. It is therefore surprising that randomness is of great help in algorithmic problem-solving. Algorithms that use randomness are often more efficient, easier to implement and easier to understand than their deterministic counterparts, and in some cases, the only efficient method we know for solving a problem is a randomized one. Randomness can also be viewed as a useful (and often limited) computational resource, similarly to time and space usage. Understanding the exact 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. Topics include (but are not limited to): randomized binary search trees, hashing-based data structures, random sampling, random walks, linear-time minimum spanning trees, cuts in graphs, verifying matrix multiplication, 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, online algorithms, ski-rental and paging, approximation and LP-rounding.
(The course will be given in English.)