Probability and Randomization in Computer Science, Master-Seminar in SS2019
Contacts:
| Jan Dreier (dreier@cs.rwth-aachen.de) |
| Henri Lotze (lotze@cs.rwth-aachen.de) |
| 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.Schedule
| 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 |
Essay
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).Content
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.