Cheminformatics

While Cheminformatics is formally a very old research field, building the foundations for the field seen from the perspective of theoretical Computer Science is not at all established research. We investigate hardness and develop conceptionally new approaches for problems arising in or motivated from chemistry. We promote modeling of chemistry with algebraic graph transformation approaches. In contrast to other methods, the atomic explicitness of our generic modeling framework often allows for a direct transfer of results from theoretical Computer Science and graph theory.

The real-world applicability of our results is very relevant for our research, but as the same underlying principles apply in settings that may considered wildly different by the practicing life-scientist, we always aim at general results and developing generic methods.

For more information, see the separate Cheminformatics Group page.

Cryptology and Complexity Theory

The efficiency of cryptographic systems and protocols has been the focus of our recent work in cryptology. The study of multiplicative complexity is being extended to general techniques for reducing the gate complexity of cryptographic functions, including AES.

We also study the advice complexity of online problems, and we study the border between tractable problems (such as P or FPT) and hard problems (such as NP-hard, W[1]-hard, W[2]-hard, etc).

Data Structures

Older work include results on relaxed balance, where we generalize search tree rebalancing operations so they can be postponed and scheduled flexibly at a provably insignificant increase in amortized complexity.

Graph Theory

Besides being a very active research area in itself, graph theory is also an important modeling tool for real-life problems. Examples include gps systems (route calculations), assigning workers to jobs, booking systems, structuring of information, scheduling construction work, etc. Many problems are best modeled as directed graphs. While undirected graph theory is very well developed with deep theories, the structure of directed graphs is much less well understood, and often the directed version of similar problems for undirected graphs is much harder to solve algorithmically.

The graph theory group at IMADA has contributed significantly to the better understanding of both structural and algorithmic aspects of directed graphs. The group works on theory development, discovering new connections between different topics, and on finding efficient solutions to difficult (NP-hard) problems for special classes of (di)graphs. We also work on parameterized algorithms for difficult problems where the goal is to develop algorithms that perform well provided that a given parameter is low.

Online Algorithms

Many real world problems have an online component, some decisions that have to be made immediately, before all related data is available, and the focus is often on minimizing resource consumption. This relates to environmental protection and resource management in general, facilitating cost-effective production and solutions. The study of online algorithms is aimed at designing and analyzing online algorithms.

It is useful to have theoretical tools that can predict algorithm performance in practice. The group has been working extensively on this, concentrating on alternatives to the standard quality measure, the competitive ratio. We have defined and are investigating relative worst order analysis, which gives results superior to those obtained with competitive analysis for several problems, including bin packing, paging, seat reservation, and many more. Newer activities include the investigation of advice complexity issues.

For more information, see the separate Online Algorithms Group page.