Schedule for Fall 2001

Topic: The Probabilistic Method

In recent years it has turned out that probabilistic techniques are very powerful in solving algorithmic problems. There are many reasons for this. First of all, randomized algorithms are often much simpler and faster than their deterministic counterparts, since it is easier to avoid bad inputs when using randomization. Furthermore, techniques such as randomized rounding are very effective in finding good approximate solutions to hard optimization problems. Also, randomized techniques have been used successfully in breaking large problems into a collection of small problems that can be solved independently. Apart from the algorithmic side, probabilistic methods have also been used as a pure proof method, for instance, in order to prove the existence of solutions to combinatorial problems. For some of these results, no alternative proof is known.

The aim of the seminar is to review the most important techniques used in the design and analysis of randomized algorithms and in probabilistic proofs. The seminar is self-contained with respect to the notation used (it will be introduced in the first two presentations). However, it is recommended that the participant has some basic knowledge in probability theory.


The meetings will take place every Wednesday at 4 p.m. in NEB 325.

Topics for presentations:


An introduction to probability theory can be downloaded here. Further references are: