Seminar Probabilistic Programming

Seminar in Theoretical CS, Summer Semester 2023


  • 16.12.2022: We are online!

Introduction and Assignment of Topics

Dates & Deadlines

April 11Topic preferences due
May 9Detailed outline due
June 7Full report due
June 27Presentation slides due
July 10 + 11Seminar talks

Note that the full 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. Describing randomized algorithms has been the classical application of these programs. Applications in biology, machine learning, quantum computing, security, and so on, have led to a rapidly growing interest in probabilistic programs in the last decade. For almost all programming languages, such as C, C#, Prolog, Haskell, Scala, LISP, a probabilistic variant does exist; and even a variant of Microsoft’s Excel has been developed – see the corresponding Wikipedia entry.


Basic knowledge in the following areas is expected:

  • Probability theory
  • Automata theory
  • Mathematical logic


1[Semantics] Jules Jacobs: Paradoxes of probabilistic programming: and how to condition on events of measure zero with infinitesimal probabilities. Proc. ACM Program. Lang. 5(POPL): 1-26 (2021) (B/M)
2[Semantics] Benjamin Aminof, Marta Kwiatkowska, Bastien Maubert, Aniello Murano, Sasha Rubin: Probabilistic Strategy Logic. IJCAI 2019: 32-38 (B/M)Daniils SmolakovsRaphaël Berthon
3[Semantics] Benjamin Aminof, Giuseppe De Giacomo, Sasha Rubin, Florian Zuleger: Beyond Strong-Cyclic: Doing Your Best in Stochastic Environments. IJCAI 2022: 2525-2531 (M)Simon FrenzRaphaël Berthon
4[Semantics] Thomas A. Henzinger, Nicolas Mazzocchi, N. Ege Saraç: Quantitative Safety and Liveness. CoRR abs/2301.11175 (2023) (B/M)
5[Verification] Barthe et al. An Assertion-Based Program Logic for Probabilistic Programs. ESOP 2018: 117-144 (B/M)
6[Verification] Raúl Pardo, Einar Broch Johnsen, Ina Schaefer, Andrzej Wasowski: A Specification Logic for Programs in the Probabilistic Guarded Command Language. ICTAC 2022: 369-387 (B/M)
7[Verification] Noam Zilberstein, Derek Dreyer, Alexandra Silva: Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning. CoRR abs/2303.03111 (2023) OOPSLA 2023 (B/M)Tim AschhoffKevin Batz
8[Verification] Peng Yan, Hanru Jiang, Nengkun Yu: On incorrectness logic for Quantum programs. Proc. ACM Program. Lang. 6(OOPSLA1): 1-28 (2022) (M)Linecker BongumbaPhilipp Schroer
9[Verification] Daneshvar Amrollahi, Ezio Bartocci, George Kenison, Laura Kovács, Marcel Moosbrugger, Miroslav Stankovic: Solving Invariant Generation for Unsolvable Loops. SAS 2022: 19-43 (M)Lisa PühlLutz Klinkenberg
10[Programming Languages] Martín Abadi, Gordon D. Plotkin: A simple differentiable programming language. Proc. ACM Program. Lang. 4(POPL): 38:1-38:28 (2020) (B/M)Markus RümenappDarion Haase
11[State Machines] Walkinshaw, N. and Hierons, R.: Second order uncertainty in state machines. IEEE Transactions on Software Engineering. 2023. (B/M)Valentin HeinenJoost-Pieter Katoen
12[Program Analysis] Susan et al.: Symbolic Execution for Randomized Programs. Proc. ACM Program. Lang. 6(OOPSLA2): 1583-1612 (2022) (B/M)Jannis FeldmannKevin Batz
13[Program Analysis] Torben Amtoft, Anindya Banerjee: A Theory of Slicing for Imperative Probabilistic Programs. ACM Trans. Program. Lang. Syst. 42(2): 6:1-6:71 (2020) (B/M)
14[Program Analysis] Marcelo Navarro, Federico Olmedo: Slicing of probabilistic programs based on specifications. Sci. Comput. Program. 220: 102822 (2022) (B/M)Umut Yigit DuralDarion Haase
15[Program Analysis] Zixin Huang, Saikat Dutta, Sasa Misailovic: Automated quantized inference for probabilistic programs with AQUA. Syst. Softw. Eng. 18(3): 369-384 (2022) (M)
16[Program Analysis] Harrison Goldstein, Benjamin C. Pierce: Parsing randomness. Proc. ACM Program. Lang. 6(OOPSLA2): 89-113 (2022) (M)Meret UnbehaunPhilipp Schroer
17[Program Analysis] Raven Beutner, C.-H. Luke Ong, Fabian Zaiser: Guaranteed bounds for posterior inference in universal probabilistic programming. PLDI 2022: 536-551 (M)
18[Program Analysis] Steven Holtzen, Guy Van den Broeck, Todd D. Millstein: Scaling exact inference for discrete probabilistic programs. Proc. ACM Program. Lang. 4(OOPSLA): 140:1-140:31 (2020) (B/M)
19[Program Analysis] Marcel Moosbrugger, Miroslav Stankovic, Ezio Bartocci, Laura Kovács: This is the moment for probabilistic loops. Proc. ACM Program. Lang. 6(OOPSLA2): 1497-1525 (2022) (B/M)Christopher BräuckerLutz Klinkenberg
20[Bayesian Networks] Miroslav Stankovic, Ezio Bartocci, Laura Kovács: Moment-based analysis of Bayesian network properties. Theor. Comput. Sci. 903: 113-133 (2022) (B/M)Viet Dung NguyenBahare Salmani
21[Bayesian Networks] Fábio Gagliardi Cozman: Graphical models for imprecise probabilities. Int. J. Approx. Reason. 39(2-3): 167-184 (2005) (B/M)Tianru LiBahare Salmani
22[Bayesian Networks] Janneke H. Bolt, Linda C. van der Gaag: Balanced sensitivity functions for tuning multi-dimensional Bayesian network classifiers. Int. J. Approx. Reason. 80: 361-376 (2017) (M)


Registration to the seminar is handled via the SuPra system.

Grading Scheme

You can access the grading scheme here:

Additional Material


Joost-Pieter Katoen