The design and analysis of exact algorithms constitutes the main research field of the Theory Group. One of our central interests lies in investigating the parameterized complexity of hard problems.

We are currently involved in two projects supported by the Deutsche Forschungsgemeinschaft (DFG):

The TAPI project (Theoretische Algorithmen auf Praktischen Instanzen, RO 927/6) focuses on a refined analysis of running times using appropriate structural properties - rather than just the size - of the input. In many cases, this approach allows for a better understanding of the computational hardness that is inherent to the problem at hand. This consequently leads to the design of new algorithms that usually outperform previous algorithms on at least an entire class of interesting instances, if not in all cases.

The second project is about intuitive algorithms (RO 927/7). It is a common phenomenon that algorithms are made more and more complex in order to ease the derivation of better and better runtime bounds. In this project, however, we aim at designing very simple, intuitive algorithms at the expense of a more difficult analysis. Of course, it takes new ideas and techniques in order to prove good runtime bounds for these nice (easy to comprehend, easy to implement, easy to verify) algorithms. In many cases, this entails proving better worst-case bounds for hitherto heuristic methods.

Furthermore, our broad range of interests include such diverse items as interactive theorem proving, circuit complexity, network analysis and concepts for peer-to-peer networks. But most of all we drink a lot of tea.