Foundations of Probabilistic Programming

Seminar in Theoretical CS, Winter Semester 2017/18


  • 21.06.2017: Student-supervisor matching is online.
  • 20.06.2017: Student-topic matching is online. Supervisor-student matching follows shortly.
  • 16.08.2017: Dates are final.
  • 16.08.2017: Tentative dates are online.
  • 27.06.2017: We are online.

Dates & Deadlines

16.10.2017 at 14:00h in Room 4201b Kick-off meeting
18.10.2017 Topic preferences due
23.10.2017 Topic notification
6.11.2017 Detailed outline due
13.11.2017 Consequenceless dropout date
4.12.2017 Seminar report due
18.12.2017 Seminar report camera-ready due
8.1.2018 Presentation slides due
22.1.2018 Presentation slides camera-ready due
5.2.2018 & 6.2.2018 Seminar talks

Note that the non-camera-ready versions of your report and your slides should be your final submission and the camera-ready versions should differ only with regard to minor remarks, comments, and corrections by your supervisor. Please feel free, however, to talk to your supervisor about submitting preliminary versions before the due dates.


This seminar covers a variety of topics in the field of probabilistic programs. Roughly speaking, probabilistic programs are like ordinary programs, with an extra feature: the ability to make some sort of probabilistic choice. Here we show how one can exploit this feature to model, for instance, a duel between two cowboys. These kind of programs are of great importance due to their wide applicability scope, which includes, amongst others, security, quantum computing, randomized algorithms and machine learning.

In this seminar we discuss the foundations of probabilistic programs, namely the underlying semantical models, as well as topics concerning the automated analysis of such programs.


Basic knowledge in the following areas is expected:

  • Semantics of programs
  • Probability theory
  • Automata theory
  • Mathematical logic
  • Previous knowledge in modelling probabilistic systems is helpful but not mandatory


Bachelor/Master Topics

  1. MCMC sampling of probabilistic programs
  2. Slicing probabilistic programs
  3. Program analysis using martingales
  4. Semantics of probabilistic programs
  5. Concurrent probabilistic programs
  6. Conditioning and recursion
  7. Probabilistic Kleene algebras
  8. Software-defined networks
  9. Expected runtimes
  10. Computational hardness
  11. Usefulness of non-termination

Master Topics

  1. Algorithmic analysis of termination
  2. Stochastic Invariants
  3. Lambda-calculus

Additional Material


Registration to the seminar is handled between Juni 30 and July 16, 2017, via the central online form.


Benjamin Kaminski, Christoph Matheja, Prof. Joost-Pieter Katoen