Ongoing Dissertation Projects

  Professor Erika Ábrahám during researching © Lukas Netz

One of the major techniques to cope with uncertainty in computer science is randomness.


Randomness has been around in theoretical computer science for decades. Back in 1963, Rabin developed a probabilistic analogon of non-deterministic finite automata. Later, he introduced randomized algorithms by providing a randomized solution to the closest pair problem in computational geometry. Enormous advancements in theory have been made since then. This includes modelling frameworks for probabilistic systems, advanced randomized algorithms, probabilistic complexity classes, and impossibility results in distributed computing, to mention a few. Still there are serious deficiencies. There is no convincing merger yet with neighbouring disciplines such as for example algorithmic optimization, hybrid systems, which are relevant to understand cyber-physical systems, and probabilistic databases. In addition, theoretical concepts on randomization have not sufficiently encroached application areas such as security and engineering. This is partly due to complexity issues but also due to the lack of adequate modelling paradigms for uncertainty in these domains. It is clear that a lifting of existing methodologies to a unified and practically relevant setting cannot be achieved in short time, but a definite progress seems possible by an integrated approach. To achieve such a new level of integration is the main objective of the UnRAVeL Research Training Group. Indeed, the framework of a research training group is an ideal setting to achieve such a progress. For the progress of computer science, this kind of integration is essential. In the current curricula and doctoral projects this merge is realized only in a rudimentary way. The Research Training Group can and will overcome this shortage of understanding between different and diverse sub-disciplines.

The qualification program is tailored towards this aim and will create a more complete type of expertise in research, needed also in industry, and will generate young scientists with lasting impact on developing trustworthy and efficient systems that can cope with uncertainty.

The research program is organized in three theoretical thrusts and an orthogonal fourth thrust as outreach to practice. The orthogonal practical thrust and three theoretical fertilise each other e.g. in that techniques from the theoretical thrusts are applied to the area of application or the application area is used as source for the formulation of theoretically interesting special cases.