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.
Meetings:
The meetings will take place every Wednesday at 4 p.m. in NEB 325.
- Sep 12: First, organizational meeting and
Introduction to Probability Theory, Part I (Christian Scheideler)
- Sep 19: Introduction to Probability Theory, Part II (Christian Scheideler)
- Further presentations will be given by the participants...
Topics for presentations:
- The first moment method [AS00, chapter 2]
- The second moment method [AS00, chapter 4]
- Chernoff bounds for independent random variables [Sch00]+[MR95]
- Chernoff bounds for dependent random variables [Sch00]
- Witness structures [Sch00]
- The Local Lemma [AS00, chapter 5]
- Algorithmic versions of the Local Lemma [Sch00]
- Two probabilistic gems: the Weierstrass approximation theorem and local
coloring [AS00]
- Discrepancy [AS00, chapter 12]
- Coding, games and entropy [AS00, chapter 14]
- Derandomization [AS00, chapter 15]
- Maximum satisfiability [MR95, section 5.2]
- Expanding graphs [MR95, section 5.3]
- Random sampling [MR95, section 9.9]
- The mincut problem [MR95, 10.2]
- Minimum spanning trees [MR95, section 10.3]
- Primality testing [MR95, section 14.6]
References:
An introduction to probability theory can be downloaded
here. Further references are:
- [AS00]: Noga Alon and Joel Spencer
The Probabilistic Method (Second Edition)
Wiley Interscience Series in Discrete Mathematics and Optimization
John Wiley and Sons, 2000.
- [MR95]: Rajeev Motwani and Prabhakar Raghavan
Randomized Algorithms
Cambridge University Press, 1995.
- [Sch00]: Christian Scheideler
Probabilistic Methods for Coordination Problems
HNI-Verlagsschriftenreihe, 2000.