Main Content

Research in the Algorithms Group

We work on the design and analysis of algorithms and data structures, with the overall aim of making working with ever larger datasets more efficient.

Our research covers the fundamental questions of theoretical computer science that follow from this goal and are answered by mathematical proofs, such as the question of the asymptotic complexity of an algorithmic problem. We also work on the engineering of algorithms and data structures to make theoretical results accessible and useful for practical applications.

Current focus areas are:

Space-efficient data structures, computing over compressed data

Representing data with minimal storage requirements has a long tradition for communication, but has also gained importance for maximizing the size of data sets that can be kept in fast memory. Unlike for traditional compression, this requires algorithms that can run directly on the compressed representation to make use of the data. We develop such methods for various problems whose space requirements adapt to the data at hand, in particular data on graphs and trees.

This work is funded by the UK's EPSRC in the project Computing over Compressed Graph-Structured Data.

Analysis of algorithms, algorithm science, adaptive algorithms

By determining exact constant factors and analyzing how the performance of algorithms and data structures depends on characteristics of the input (adaptive analysis), we develop improvements for fundamental building blocks of computer science like sorting, selecting, and searching in dictionaries.

This includes engineering implementations of algorithms and their empirical analysis (algorithm science), ideally leading to practical adoption as in the case of Powersort, the new sorting method in Python.

For further information, see www.wild-inter.net, which has a complete list of publications and talks.