Field of research

Efficient algorithms and data structures are the basis of all nontrivial computer applications. Algorithmics – the systematic development of efficient algorithms – is therefore crucial for transforming technological potential into applications that are important for technology, business, science, and our daily lives. At the institute of theoretical informatics, our group focuses on the "basic toolbox" of methods that are needed in many applications, e.g., sorting, index data structures, route planning in graphs, or partitioning graphs. The group also develops open source software for solving such problems and uses its know-how to solve selected concrete application problems.

At first glance, it is surprising that despite decades of research there are still open problems within the basic toolbox. There are two reasons for this. On the one hand, in the last years we are facing an explosive growth of data sets that can only be handled using increasingly complex parallel hardware. This also implies additional basic toolbox problems like load balancing or communication algorithms. On the other hand, a huge gap between theory and practice has emerged. Theoreticians develop sophisticated solutions with strong performance guarantees for simplified settings, but all too often ignore implementability or the realities of applications and modern hardware. For their part, practitioners often ignore theoretical insights and methods and thus arrive at ad-hoc solutions without any discernible performance guarantees. Therefore, the methodology of algorithm engineering is central for our group which helps to overcome the above challenges by integrating modeling, design, analysis, implementation, and experimental evaluation.

News

You can find older news here.

KaMPIng auf SC'24 ausgezeichnetLillie Elliot, SC Photography
KaMPIng auf SC'24 ausgezeichnet

Der C++ MPI-Wrapper KaMPIng wurde von Tim Niklas Uhl auf der SC'24 in Atlanta vorgestellt und mit dem Best Reproducibility Advancements Award ausgezeichnet.

mehr
Defense Hans-Peter Lehmann
Hans-Peter Lehmann defends dissertation

24.10.2024: Hans-Peter Lehmann receives his PhD, his dissertation is entitled "Fast and Space-Efficient Perfect Hashing".

Golden Spike
HoreKa project receives "Golden Spike Award"

11.10.2024: The HPC project "Scalable Discrete Algorithms for Big Data Applications" on HoreKa has been awarded with the "Golden Spike Award" at the 27th HLRS Results and Review Workshop.

Award
Dominik Schreiber receives awards

28.08.2024: Dominik Schreiber receives two awards for his dissertation "Scalable SAT Solving and its Application": the joint dissertation award from the German Informatics Society, the Austrian Computer Society, and the Swiss Informatics Society; and the Fahiem Bacchus PhD Award in Satisfiability.

more
bild
MPI library KaMPIng published

17.06.2024: The first version of the C++ MPI wrapper KaMPIng has been released and presented at SPAA. The full paper has been accepted at supercomputing (SC).

more
Bild
Daniel Funke defends dissertation

30.11.2023: Daniel Funke receives his PhD, his dissertation is entitled "Algorithms for Triangles, Cones & Peaks".

Bild
Dominik Schreiber defends dissertation

17.11.2023: Dominik Schreiber receives his PhD, his dissertation is entitled "Scalable SAT solving and its application".

Bild
Demian Hespe defends dissertation

21.07.2023: Demian Hespe receives his PhD, his dissertation is entitled "Enabling Scalability: Graph Hierarchies and Fault Tolerance".

Bild
Tobias Heuer defends dissertation

26.10.2022: Tobias Heuer receives his PhD, his dissertation is entitled "Scalable High-Quality Graph and Hypergraph Partitioning".

Bild
Mallob wins SAT Competition

10.07.2020: The massively parallel and distributed SAT solver "mallob" by Dominik Schreiber wins the first prize of the Cloud Track of the international SAT Competition 2020 by a significant margin.

ERC
ERC Advanced Grant

31.03.2020: Peter Sanders receives an ERC Advanced Grant for his project „ScAlBox – Engineering Scalable Algorithms for the Basic Toolbox“. For further information, please see the websites of the department of informatics (German only) and the European Research Council. The subject of this project is developing scalable basic algorithmic tools that scale to the largest inputs and to very large numbers of processors.

Bild
ESA "Test-of-Time" Award

08.09.2020: Peter Sanders and Ulrich Meyer (University of Frankfurt) gave a talk at the European Symposium on Algorithms 2020 about their paper that won the "Test-of-Time"-award 2019 in March. You can find the talk here.

more
Bild
ALENEX Steering Committee

06.01.2020: Peter Sanders was elected chair of the steering committee of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX). ALENEX is the premier North American conference on the topic and one of the most important ones worldwide.