Seminar in Theoretical CS, Summer Semester 2019

News

• 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, 13:00	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.

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. 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.

Prerequisites

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

Topics

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
   • Supervisor: Joshua Moerman
   • Student: Tom Biskup
2. Probabilistic couplings
   • Supervisor: –
   • Student: –
3. Termination analysis with martingales
   • Supervisor: –
   • Student: –
4. Improving program testing by probabilistic programming
   • Supervisor: Marcin Szymczak
   • Student: Florian Frantzen
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
   • Literature: N. Polikarpova, I. Sergey: Structuring the synthesis of heap-manipulating programs. POPL 2019
   • Supervisor: –
   • Student: –
3. Synthesis of probabilistic programs
   • Literature: A.V. Nori, S. Ozair, S.K. Rajamani, D. Vijaykeerthy: Efficient synthesis of probabilistic programs. PLDI 2015
   • Supervisor: Marcin Szymczak
   • Student: Bram Kohlen

Additional Material

Registration

Registration to the seminar is not possible anymore.

Contact

Joost-Pieter Katoen, Thomas Noll