Seminar in Theoretical CS, Winter Semester 2024/25
News
- 06.06.2024: We are online!
Introduction and Assignment of Topics
- Slides of introduction (TBA)
Dates & Deadlines
| TBA | Topic preferences due |
| TBA | Detailed outline due |
| TBA | Full report due |
| TBA | Presentation slides due |
| TBA | 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 from Last Edition
Note: We will update this page with topics for this edition shortly. Here are last editition’s 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) | ||
| 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) | ||
| 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) | ||
| 8 | [Verification] Peng Yan, Hanru Jiang, Nengkun Yu: On incorrectness logic for Quantum programs. Proc. ACM Program. Lang. 6(OOPSLA1): 1-28 (2022) (M) | ||
| 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) | ||
| 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) | ||
| 11 | [State Machines] Walkinshaw, N. and Hierons, R.: Second order uncertainty in state machines. IEEE Transactions on Software Engineering. 2023. (B/M) | ||
| 12 | [Program Analysis] Susan et al.: Symbolic Execution for Randomized Programs. Proc. ACM Program. Lang. 6(OOPSLA2): 1583-1612 (2022) (B/M) | ||
| 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) | ||
| 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) | ||
| 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) | ||
| 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) | ||
| 21 | [Bayesian Networks] Fábio Gagliardi Cozman: Graphical models for imprecise probabilities. Int. J. Approx. Reason. 39(2-3): 167-184 (2005) (B/M) | ||
| 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
- Report template
- Presentation template
- How to Write a Seminar Paper
- Ethische Richtlinien für das Verfassen wissenschaftlicher Arbeiten
- How to Give Presentations
- Introduction to LaTeX