CheminformaticsWhile 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 TheoryThe 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-hard, W-hard, etc).
Data StructuresOlder 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.
Online AlgorithmsMany 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.