Foundations of Probabilistic Programming/Program Synthesis

Seminar in Theoretical CS, Summer Semester 2019


  • 18.12.2019: We are online.

Dates & Deadlines

03.04.2018, 15:00 Kick-off meeting at seminar room of i2 (building E1, room 4201b)
05.04.2019 Topic preferences due
06.05.2019 Detailed outline due
03.06.2019 Full report due
01.07.2019 Presentation slides due
11.07.2019 (afternoon) 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.

This seminar extends the foundations of probabilistic programs as introduced in the preceding lecture in Winter Semester 2018/19 by studying refined semantical models  and advanced methods for 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 probabilistic programming is very helpful


Foundations of Probabilistic Programming

These topics are based on a draft book “Foundations of Probabilistic Programming” that includes surveying chapters by different (sets of) authors on the following topics (amongst others). The material will be made available as paper copies.

  1. Logical essentials of Bayesian reasoning
  2. Probabilistic couplings
    • Supervisor:
    • Student:
  3. Termination analysis with martingales
    • Supervisor:
    • Student:
  4. Improving program testing by probabilistic programming
  5. Concentration measures
    • Supervisor:
    • Student:

Program Synthesis

  1. Syntax-guided synthesis
    • Literature: R. Alur, R. Bodik, G. Juniwal, M.M.K. Martin, M. Raghothaman, S.A. Seshia, R. Singh, A. Solar-Lezama, E. Torlak, A. Udupa: Syntax-guided synthesis. FMCAD 2013
    • Supervisor: Joshua Moerman
    • Student: Marvin Jansen
  2. Synthesis of pointer programs
  3. Synthesis of probabilistic programs

Additional Material


Registration to the seminar is not possible anymore.


Joost-Pieter Katoen, Thomas Noll