Seminar Probabilistic Programming

Seminar in Theoretical CS, Summer Semester 2023

News

16.12.2022: We are online!

Introduction and Assignment of Topics

Slides of introduction (TBA)
Intro Slides

Dates & Deadlines

April 11	Topic preferences due
May 9	Detailed outline due
June 7	Full report due
June 27	Presentation slides due
July 10 + 11	Seminar 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.

Overview

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.

Prerequisites

Basic knowledge in the following areas is expected:

Probability theory
Automata theory
Mathematical logic

Topics

#	Topic	Student	Supervisor
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 Smolakovs	Raphaë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 Frenz	Raphaë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 Aschhoff	Kevin 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 Bongumba	Philipp 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ühl	Lutz 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ümenapp	Darion Haase
11	[State Machines] Walkinshaw, N. and Hierons, R.: Second order uncertainty in state machines. IEEE Transactions on Software Engineering. 2023. (B/M)	Valentin Heinen	Joost-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 Feldmann	Kevin 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 Dural	Darion 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 Unbehaun	Philipp 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äucker	Lutz 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 Nguyen	Bahare 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 Li	Bahare 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

Registration to the seminar is handled via the SuPra system.

Grading Scheme

You can access the grading scheme here: https://moves.rwth-aachen.de/wp-content/uploads/seminar_grading_scheme.pdf

Additional Material

Contact

Joost-Pieter Katoen