Research Training Group UnRAVeL (UNcertainty and Randomness in Algorithms, VErification, and Logic, DFG 2236/1)

**** New UnRAVeL – Website is now available *****

 

 

Research Programme

UnRAVeL 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 analogue of non-deterministic finite automata. Later, he introduced randomised algorithms by providing a randomised 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 randomised 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 e.g., algorithmic optimisation, hybrid systems (which are relevant to understand cyber-physical systems), and probabilistic databases. In addition, theoretical concepts on randomisation 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 RTG UnRAVeL. 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 realised only in a rudimentary way. The RTG can and will overcome this shortage of understanding between different and diverse (sub-) disciplines. The qualification programme 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.

Possible Dissertation Projects

Information about the possible dissertation projects can be found on a separate page.

Principal Investigators

  • Erika Ábrahám: hybrid systems, probabilistic systems, satisfiability checking
  • Jürgen Giesl: termination analysis, run-time analysis, term rewriting, theorem proving
  • Erich Grädel: logic and algorithms, descriptive complexity, game theory, logics for uncertainty and imperfect information, quantitative logics
  • Martin Grohe: logic in computer science, algorithms and complexity, database theory, graph theory
  • Joost-Pieter Katoen: probabilistic verification, probabilistic programming, semantics, concurrency theory, model checking
  • Gerhard Lakemeyer: robotics, artificial intelligence, knowledge representation, action logics
  • Christof Löding: automata theory, synthesis, games
  • Ulrike Meyer: malware detection, privacy enhancing technologies, wireless security
  • Nils Nießen: railway operation, railway signalling, transport economics
  • Britta Peis: discrete optimization, algorithmic game theory, network flows
  • Pascal Schweitzer: certifying algorithms, graph theory, group theory, online algorithms
  • Gerhard Woeginger: approximation algorithms, combinatorial optimization, planning and scheduling, complexity theory

3-Minutes-Explanation of RTG UnRAVeL