Doctoral Privatissima

We recommend that you contact the organizers directly via e-mail if you are interested in one of the courses on offer


Summer Semester 2016

State of the Art Linear Programming Theory

Andreas Karrenbauer

Details can be found here.


Basics of Scientific Writing and Presenting

Verena Wolf

Details can be found here.


Theory and Practice of Garbled Circuits

Dominique Schröder

This doctoral privatissimum discusses the theory and practice of garbled circuits (GC).

GC are an amazing technique to securely compute any efficiently computable function in a two party protocol. That is, Alice with input x and Bob with input y would like to compute a function f(x,y) such that the individual inputs remain private and both parties only learn the output of the function.

The structure would be the following:

– Definition of secure two-party computation

– Semi-honest and malicious security

– Foundation of GC

– OT extension

– Efficiency of GC: freeXOR, half gates,…

– Information theoretic GC

– ….

Interest and knowledge in cryptography and facility with mathematics will be helpful.

First meeting: 27.04.2016, E9.1, room 1.08 at 10am.

How to apply:

Send an email to Dominique Schröder with the following information:

– your name and matriculation

– a motivational statement why you want to participate

– your transcript of records


Summer Semester 2015

Oblivious RAM and Private Information Retrieval

Matteo Maffei

Block course August 31 to September 11, 9am–1pm

In this doctoral privatissimum we will study literature on oblivious RAM (ORAM) and private information retrieval (PIR) in depth. ORAM was proposed in 1996 by Goldreich and Ostrovsky as a technique to conceal the CPU’s access pattern on the RAM from someone who monitors all RAM accesses. PIR was invented by Chor et al. in 1998 as a mechanism by which a user who queries a database does not reveal to the database holder which index she queried. Both areas are still constantly improved and there exist a plethora of different schemes in either topic. The goal of this course is to obtain a clear understanding and to categorize the different tech- niques to achieve ORAM and PIR. Some schemes only differ in details but even slight changes have shown to improve the respective scheme by orders of magnitude.


Most importantly, interested students should be highly motivated. We recommend to have taken at least one of (preferably more) Security, Cryptography, and Privacy-Enhancing Technologies. More- over, we expect a profound knowledge in foundations of algorithms and algebra.

How to apply

Send an email to Prof. Maffei with the following information:

– your name and matriculation

– a motivational statement why you want to participate

– your transcript of records



Bernd Finkbeiner 

Trace properties, i.e., sets of execution traces, have long been used
to specify the correctness of computer systems. There are, however,
important properties that are impossible to describe by referring to
individual execution traces. Information flow policies, which
characterize the circumstances under which an external observer can
distinguish two executions, are of this type. Other examples include
symmetric access to a shared resource, and the correctness of encoders
and decoders for error resistant codes. Because these properties are
properties of sets of execution traces, rather than properties of
individual traces, they are called hyperproperties.
In this doctoral privatissimum, we will survey and criticize different
ways to specify and verify hyperproperties. Previous exposure to
information flow control and/or automated verification is helpful but
not a requirement.

If you are interested, please send a quick message
to finkbeiner(at)

–> First meeting: Wednesday, May 27, 2015, 12:00 noon, Room E1.3/506

Winter Semester 2014/15

Infinite Games

Bernd Finkbeiner with Martin Zimmermann

Many of todays problems in computer science are no longer concerned with programs that transform data and then terminate, but with non-terminating systems which have to interact with a possibly antagonistic environment. Over the course of the last fifty years it turned out to be very fruitful to model and analyze such systems in a game-theoretic framework, which captures the antagonistic and strategic nature of the interaction between the system and its environment.

In this doctoral privatissimum we study graph-based two-player games of infinite duration, which model this interaction. We focus on current research topics like computing optimal strategies (e.g., ones that answer requests as soon as possible or minimize energy-consumption), computing small strategies, and also tradeoffs between these quality measures. Furthermore, we consider a variation of the basic setting in which we allow asynchronous strategies that allow one player to obtain a lookahead on her opponent’s moves, so-called delay games.

The goal of this privatissimum is to learn about the state-of-the-art in infinite games with quantitative winning conditions to be able to discuss questions like „do I need more memory to play optimally?“, „can I play better if I get a lookahead on my opponent’s moves?“, and „can I save memory if I get a lookahead on my opponent’s moves?“.

The exact format and time will depend on the constraints of the participants. Interested students should please contact (zimmermann(at)


Dynamic Programming and Optimal Control

Holger Hermanns

Interested students should please contact Prof. Hermanns directly (hermanns(at)


Categorical Logic

Derek Dreyer

In this privatissimum, we will study the basics of category theory with an eye towards a particular application: how to use it to build useful models of modern higher-order logics with guarded recursive predicates.  Such models underlie a number of the most advanced program logics being developed today, e.g. higher-order concurrent separation logics like iCAP (ESOP’14) and Iris (POPL’15).  Along the way, we will pick up as much category theory as we need.  (The
instructor will be learning along with the students!)

Concretely, we will work primarily from two texts: Steve Awodey’s „Category Theory“ textbook, and Lars Birkedal & Ales Bizjak’s tutorial notes on „A Taste of Categorical Logic.“  We will meet for 90 minutes, twice a week, from November through January, to discuss the texts and work through problems.  Both texts also include many exercises, which will be assigned as homework.  Significant self-study will be required.

I will hold an initial meeting on Wednesday or Thursday, October 29 or 30, to discuss the course.  We can then decide on a time that is suitable for all who are attending.  Those who are interested should please let me know when they are available to attend the initial meeting on October 29 or 30.

Winter Semester 2013/14

Web Security

Matteo Maffei

Organizational Meeting: Thursday March 20 at 2pm in E1.7, room 2.10

Time: Every day, from Monday March 24 until Friday April 11, at 10am.

Place: To be defined.

Office Hours: Monday 4-6 pm, E1.7, room 2.09

Form/Credits: Doctoral Privatissima, 6 ECTS

Language: English

Further Details:

Last years have seen a proliferation of attacks (e.g. cross site scripting, SQL injections, and cookie stealing) on web services. The attack surface is extraordinarily large and complex, and it includes the network as well as the application layer: attacks may exploit the nasty semantics of JavaScript applications, flaws in cryptographic protocols, specific features of HTML5, DNS vulnerabilities, and more. Due to the strong influence of the web on the society and due to the increasing number of personal data populating the Internet, such attacks have a devastating harm potential. For this reason, understanding how web services may be attacked and defended is of paramount importance.

Web security is an emerging, and nonetheless extraordinarily active, research field. In this doctoral privatissima, you will get a deep understanding of the state-of-the-art, by critically analysing the most significant research papers published in the top-tier security conferences in the last years. We will focus on both attacks and defence techniques, with the ultimate aim of improving the actual web safeguard and drawing hints for future research.


Human-Computer Interaction

Antti Oulasvirta

(6 ECTS, ungraded)

The Human-Computer Interaction group offers doctoral privatissima to students in the preparatory phase. This is an excellent chance to learn about HCI and apply CS-skills into user interface design and modeling problems. The student will plan and execute a small research project in collaboration with other group members. Supervision and feedback will be provided.

In the upcoming semester, open topics include (but are not limited to):

* „iFace“: Designing interactions using real-time computer vision tracking of facial gestures.

* „Model Anything“: Interactive visualization of nonlinear regression model classes (together with the group of Tino Weinkauf).

* „Bye bye Qwerty“: Optimization of physical keyboard layouts for improved typing speed.

* „Is it in Edit or File?“: Data-driven prediction of expectations and semantics in menu systems.

In addition to the mini-project, the student is assigned and examined on a personalized list of readings related to the selected topic. Moreover, students can participate in weekly group meetings, „clinic“ sessions (soft skills in HCI), and take part in the reading groups.

There is no deadline for applications. Maximum 2 students can be hosted per semester. For consideration, please send a brief letter of interest, CV, and course transcripts to


Spectral Graph Theory

He Sun

To be offered as a block course 3-22 March 2014.

Spectral Graph Theory studies the matrix representations of graphs, and offers many unexpected and beautiful connections between two apparently unrelated branches of mathematics: Algebra and Graph Theory. Due to this connection, various algebraic questions can be reduced to graph problems, and this insights lead to some new techniques in designing graph algorithms.

This block course focuses on advanced topics in spectral graph theory, and recent breakthroughs of graph algorithms that are based on spectral techniques. Some topics include:

· Graphs and Groups

· Matrix Theory

· Eigenvalues and Interlacing

· Explicit Constructions of Expanders

· High-Order Cheeger Inequalities

· Spectral Sparsification of Graphs



Summer Semester 2013

Multimedia coding for broadband and broadcast networks

Goran Petrovic with Thorsten Herfet

Multimedia streaming, a real-time delivery of compressed multimedia data is ubiquitous in today’s broadband and broadcast networks. However, an efficient utilization of network resources (bandwidth, processing power, energy) in multimedia streaming is still an active research area. Central to this area are efficient multimedia compression and streaming algorithms. The main topics of our privatissimum are the theoretical background, design and implementation of such algorithms. Specifically, we combine topics from modern video and audio compression, network congestion control, adaptive streaming and multiview 3D systems. We cover these topics with a mix of selected book chapters and research papers. We expect active class participation and in-class discussions from students. Knowledge of the basics of multimedia transmission and compression (acquired in courses such as TC2, FMI, or similar) is helpful, but not mandatory.

Target duration: 12-13 Modules
First meeting: week 29.04.13 – 03.05.13
Date and location: TBA

To register, please email to:
Goran Petrovic
Telecommunications Lab
Campus C6.3, Room 10.09
Saarland University



Raimund Seidel

Topic: Hashing is a powerful idea with applications ranging from data structures to cryptography. Although the idea is simple, its perfect realization has proven surprisingly difficult and seems to require a non-trivial mix of randomness and determinism. It is still a very active area of research. In this doctoral privatissimum we will various research papers on this subject.
Interest and knowledge in algorithms and data structures as well as facility with mathematics will be helpful.

A first, organizing meeting will be on Monday, 22 April 2013, 12:15, Bld. E1 3, Rm. 415.

Operating System Design and Implementation

Björn Brandenburg

Topic: Operating systems form the basis of virtually all modern computing platforms (with the notable exception of some resource-constrained, single-purpose embedded systems). Importantly, the design and implementation of the underlying operating system is crucial to the performance and reliability characteristics of the entire system. The topic of this doctoral privatissimum is recent advances in OS design and implementation, with a particular focus on scalability, energy efficiency, and reliability in the multi- and many-core age.

Format: Regular weekly meetings, tentatively scheduled for Fridays 2-3pm, SS 2013.