Probability and Randomization in Computer Science, Master-Seminar in SS2019


Jan Dreier (
Henri Lotze (
Peter Rossmanith

Kick-off Meeting

The slides from the kick-off meeting are available here.

Place and Time

The seminar will take place Thursdays at 14:40 in our seminar room 4101.


Date Topic Student
9. May Basics Florian Drux
16. May Bounds Yat Wai Wong
16. May Martingales Felix Holler
23. May Hypothesis Testing Hayyan Helal
6. June Resampling Abdallah Atouani
27. June Randomized Computation Alexander Bork
4. July Isolation Lemma Yassin Bahloul
15. August Schöning's Algorithm Sebastian Riebeling


Please hand in your essay until August, 11th. It should be in LaTeX and should not exceed 8 pages (excluding references). Please use this template (or something equivalent).


Some advanced techniques in algorithmics heavily use randomization and methods from probability theory. In this seminar we will look at several classical techniques and recent papers that are particularly relevant and impressive. To be able to participate you need a good background in theoretical computer science, probability theory, and discrete math.

A possible list of topics that is not complete contains random walks, Markov chains, Chernoff bounds, martingales, zero-one laws, Lovász local lemma, the isolation lemma, color coding, Boltzmann samplers, Schöning's algorithm, zero knowledge proofs, randomized prime testing, etc. We will stress the algorithmic applications rather than the mathematical theory.

Every participant will give a talk, with a following discussion, and prepare a short written essay summarizing the most important aspects.