Back

Randomized Algorithms

Wolfgang Merkle
Section: Computation
Level: Introductory

Description

Given a graph, is there are a subset S of its vertices such that at least half of the edges connect a vertex in S and a vertex not in S? A simple argument from elementary probability theory shows that if we flip a fair coin for each vertex in order to decide whether the vertex should be in S or not, then with non-zero probability we obtain a set S as desired (and thus, in particular, there is such a set S). This way of tackling a problem is known as the probabilistic method, a method that often yields surprisingly elegant and elementary arguments even if explicit constructions apparently need to be rather involved. Furthermore, as in the example above, the probabilistic method frequently leads to randomized algorithms that are comparatively simple and easy to verify.

The first part of the course gives an introduction to randomized algorithms and to standard techniques for their derandomization. The material will be presented by means of simple examples from graph theory.

The second part of the course presents applications of the probabilistic method to the construction of logical models and briefly discusses related issues such as Rado-graphs and 0-1 laws.

Prerequisites

The course requires only a rudimentary understanding of a few basic concepts from probability theory such as expectation and independence of random variables. These concepts will be shortly reviewed at the beginning of the course. The second part on logic requires in addition some basic understanding of first-order logic.

Materials

PDFlecture notes

Lecturers

Dr. Wolfgang Merkle
Universität Heidelberg
Mathematisches Institut
Im Neuenheimer Feld 294
D-69120 Heidelberg
Tel. +49-6221-54 5409
Fax. +49-6221-54 4465
merkle@math.uni-heidelberg.de
http://math.uni-heidelberg.de/logic/merkle/merkle.html