Prof. Dr. Tobias Friedrich

Power of Randomness

MSc Seminar - Winter 2017/18


Randomness has proven to be a powerful tool in the design and analysis of algorithms. This seminar aims to bring students in the forefront of today research topics, by studying recent research papers in the area of randomness in computation.

Some proposed topics:

  • Continuous distributions (Poisson, exponential) and queuing theory.
  • Lovasz local lemma.
  • Markov chain Monte Carlo method (canonical paths, approximating number of matchings, approximating the permanent).
  • The correlation decay method for sampling independent sets.
  • Phase transitions in random structures (random SAT, random graphs).
  • Hash functions.
  • Number theoretic randomised algorithms.
  • Sample complexity of machine learning algorithms.


This is a master-level seminar. There will be no restriction in the number of participants. The seminar will be held in English. Participants should be willing to give talks in English and to actively participate in discussing the topics.


Basic probability theory is required. Moreover we expect motivated, interactive and creative presentations.

Seminar mode

The seminar is intended to be interactive and student focused. Each participant will choose one topic to present in an interactive and engaging way. The participants will either have to write a short summary of their topic that will be published to all the participants of the course, or choose to present a second topic.

The exact seminar mode depends on the number of participants and will be announced during the first session.


The grading will depend on the quality of the seminar session lead by the participants.