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.
24.10.2024: Hans-Peter Lehmann receives his PhD, his dissertation is entitled "Fast and Space-Efficient Perfect Hashing".
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.
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
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
30.11.2023: Daniel Funke receives his PhD, his dissertation is entitled "Algorithms for Triangles, Cones & Peaks".
17.11.2023: Dominik Schreiber receives his PhD, his dissertation is entitled "Scalable SAT solving and its application".
21.07.2023: Demian Hespe receives his PhD, his dissertation is entitled "Enabling Scalability: Graph Hierarchies and Fault Tolerance".
26.10.2022: Tobias Heuer receives his PhD, his dissertation is entitled "Scalable High-Quality Graph and Hypergraph Partitioning".
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.
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.
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
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.