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.