Probabilistic Programming (Seminar)

Seminar in Theoretical CS, Winter Semester 2020/21

News

Introduction and Assignment of Topics

Dates & Deadlines

30.10.2020Topic preferences due
30.11.2020Detailed outline due
11.01.2021Full report due
01.02.2021Presentation slides due
08./09.02.2021Seminar 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.

The topics considered in this seminar are mostly based on a draft of the forthcoming book Foundations of Probabilistic Programming (edited by Gilles Barthe, Joost-Pieter Katoen, and Alexandra Silva and freely accessible). It contains 15 surveying chapters by different (teams of) authors, divided into five parts:

  1. Semantics,
  2. Verification.,
  3. Logic,
  4. Security, and
  5. Programming languages.

Additionally, we include some papers on static analysis of probabilistic programs as this research area is not covered by the book.

Prerequisites

Basic knowledge in the following areas is expected:

  • Probability theory
  • Automata theory
  • Mathematical logic

Schedule of Talks

TimeMonday, February 8Tuesday, February 9
09:00-10:30Leon Barth, Jonathan du Mesnil, Thomas VogtHannah Mertens, Jonas Deutsch, Jan Wieczorek
11:00-12:30Jonathan Lehmkuhl, Sonja Skiba, Lena VerschtInokentiy Babushkin, Caroline Jabs, Minh Nghi Phan

Topics

(Move the cursor over the entry to see the corresponding abstract.)

Chapters of Foundations of Probabilistic Programming:

  1. [Semantics] Fredrik Dahlqvist, Dexter Kozen, Alexandra Silva: Semantics of Probabilistic Programming: A Gentle Introduction (44 pages)
  2. [Semantics] Sam Staton: Probabilistic Programs as Measures (35 pages)
    • Student: –
    • Supervisor: –
  3. [Semantics] Daniel Huang, Greg Morrisett, Bas Spitters: An Application of Computable Distributions to the Semantics of Probabilistic Programs (50 pages)
    • Student: –
    • Supervisor: –
  4. [Semantics] Ugo Dal Lago: On Probabilistic Lambda-Calculi (27 pages)
  5. [Verification] Gilles Barthe, Justin Hsu: Probabilistic Couplings from Program Logics (43 pages)
  6. [Verification] Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja: Expected Runtime Analysis by Program Verication (39 pages)
  7. [Verification] Krishnendu Chatterjee, Hongfei Fu, Petr Novotný: Termination Analysis of Probabilistic Programs with Martingales (41 pages)
  8. [Verification] Sriram Sankaranarayanan: Quantitative Analysis of Programs with Probabilities and Concentration of Measure Inequalities (40 pages)
    • Student: –
    • Supervisor: –
  9. [Logic] Bart Jacobs, Fabio Zanasi: The Logical Essentials of Bayesian Reasoning (40 pages)
  10. [Logic] Giorgio Bacci, Radu Mardare, Prakash Panangaden, Gordon Plotkin: Quantitative Equational Reasoning (30 pages)
  11. [Security] Jose Manuel Calderon Trilla, Michael Hicks, Stephen Magill, Piotr Mardziel, Ian Sweet: Probabilistic Abstract Interpretation: Sound Inference and Application to Privacy (31 pages)
  12. [Security] Jeremy Gibbons, Annabelle McIver, Carroll Morgan, Tom Schrijvers: Quantitative Information Flow with Monads in Haskell (65 pages)
  13. [Programming languages] Lampropoulos Leonidas, Benjamin C. Pierce, Li-yao Xia, Diane Gallois-Wong, Catalin Hritcu, John Hughes: Luck: A Probabilistic Language for Testing (44 pages)
  14. [Programming languages] Michael Carbin, Sasa Misailovic: Programming Unreliable Hardware (39 pages)
  15. [Programming languages] Andrew D. Gordon, Claudio Russo, Marcin Szymczak, Johannes Borgström, Nicolas Rolland, Thore Graepel, Daniel Tarlow: Tabular: Probabilistic Inference from the Spreadsheet (47 pages)
    • Student: –
    • Supervisor: –

Static analysis:

  1. Clemens Dubslaff, Andrey Morozov, Christel Baier, Klaus Janschek: Reduction Methods on Probabilistic Control-flow Programs for Reliability Analysis, arXiv:2004.06637, 2020
    • Student: –
    • Supervisor: –
  2. Chung-Kil Hur, Aditya V. Nori, Sriram K. Rajamani, Selva Samuel: Slicing Probabilistic Programs. ACM SIGPLAN Notices, 2014
  3. Di Wang, Jan Hoffmann, Thomas Reps: PMAF: An Algebraic Framework for Static Analysis of Probabilistic Programs, PLDI 2018
    • Student: –
    • Supervisor: –
  4. Van Chan Ngo, Quentin Carbonneaux, Jan Hoffmann: Bounded Expectations: Resource Analysis for Probabilistic Programs, PLDI 2018, 496-512
    • Student: –
    • Supervisor: –

Additional Material

Registration

Registration to the seminar is possible via the central registration procedure of the CS Department.

Contact

Thomas Noll