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

July/09/2021 In the AWS environment of the International SAT Competition 2021, the scalable SAT solving system Mallob by Dominik Schreiber dominates the Cloud Track (on 1600 hardware threads) and also proves to be highly competitive in the Parallel Track (on 64 hardware threads). All results can be found here.

September/08/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.

July/10/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.

March/31/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.

March/16/2020: The Algorithms II written exam on Friday, March 20 2020, was canceled. For further information, please see here.

March 2020: Peter Sanders (together with Ulrich Meyer from the University of Frankfurt) will be awarded the 'Test-of-Time Award' of the European Symposium on Algorithms 2019 (ESA) at ESA 2020. ESA is the premier European conference on algorithms research. For further information, please see here.

Jan/08/2020: Peter Sanders was appointed PC chair for the European Symposium on Algorithms (ESA) (track B - Algorithm Engineering). ESA is the premier European conference on algorithm engineering.

Jan/06/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.

Dec/27/2019: Prof. em. Dr. Peter Deussen, one of the founders of the Department of Informatics in Karlsruhe, passed away aged 84. He was Prof. Dr. Peter Sanders' predecessor in the professorship for Theoretical Informatics. For further information please see here.

Dec/12/2019: The Gauss Centre for Supercomputing has granted 22.5 million core-hours of computing time for our project MasDA: Massively Scalable Discrete Algorithms for the Basic Toolbox.

Nov/22/2019: Prof. Dr. Peter Sanders was re-elected to the DFG Review Board and received the highest number of votes. For further information, please see here.

Oct/08/2019: Best Paper Award SPIRE 2019 for "COBS: A Compact Bit-Sliced Signature Index" by Timo Bingmann, Phelim Bradley, Florian Gauger, and Zamin Iqbal. More information.

Sep/11/2019: Two current and two former members of the group win the first place of the fourth "Parameterized Algorithms and Computational Experiments Challenge" (PACE). For further information, please see here (German only).

Jun/19/2019: Dr. Timo Bingmann was awarded the Uniserv Research-Prize "Algorithms for Efficient Data-Processing" for the best dissertation in the field of fast algorithms. More information.

 

More...