For more news please see the front page and the scientists' homepages.
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.
Michael Axtmann receives his PhD, his dissertation is entitled 'Robust Scalable Sorting'.
Lorenz Hübschle-Schneider receives his PhD, his dissertation is entitled 'Communication-Efficient Probabilistic Algorithms: Selection, Sampling, and Checking'.
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.
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.
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.
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. The ESA Test-of-Time Award (ToTA) recognizes excellent papers in algorithms research that were published in the ESA proceedings 19 to 21 years ago which are still influential and stimulating for the field today. For 2019, the Award Committee selected
Ulrich Meyer, Peter Sanders
Delta-Stepping: A Parallel Single Source Shortest Path Algorithm.
Proceedings of ESA 1998, pp. 393-404.
Also appeared in
J. Algorithms 49(1): 114-152 (2003)
Laudation of the Award Committee
The paper presents an ingenious algorithm, dubbed Delta-stepping, for the Single-Source Shortest Path Problem (SSSP). This problem is well understood in the sequential setting (i.e., Dijkstra's algorithm) but its ubiquitous applications call for efficient parallelizations. Most of the sequential SSSP algorithms are based either on label-setting or on label-correcting methods. Label-setting algorithms, like Dijkstra's algorithm, settle at each iteration the distance label of one vertex. Label-correcting algorithms work instead by relaxing edges incident to unsettled vertices: all labels are temporary until the final step, when they all become permanent. In spite of the great practical performance of label-correcting methods, label-setting algorithms have been known to be asymptotically superior. In their paper, Meyer and Sanders show how to fill this gap by presenting Delta-stepping, a new label-correcting algorithm for SSSP which runs in optimal linear time with high probability for a large class of graphs with random edge weights. They further provide an efficient parallel implementation of their Delta-stepping algorithm, which has been a reference method and has inspired much subsequent work in parallel algorithms for many years.
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.
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.
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.
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.
Sebastian Schlag receives his Phd, his dissertation is entitled 'High-Quality Hypergraph Partitioning'.
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.
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).
Dr. Timo Bingmann receives the Uniserv research award 'Algorithms for efficient data processing' for his dissertation "Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools". For further information please see here (German only).
Yaroslav Akhremtsev receives his Phd, his dissertation is entitled 'Parallel and External High Quality Graph Partition'.
Timo Bingmann receives his Phd, his dissertation is entitled 'Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools'.
Best Paper Award IPDPS 2018: Communication-free Massively Distributed Graph Generation by D. Funke, S. Lamm, P. Sanders, C. Schulz, D. Strash, M. von Looz
Unfortunately, Prof. Sanders' lecture "Algorithm Engineering" is NOT taking place in the summer semester of 2018. It will likely be on the schedule again for the summer semester of 2019.
Jochen Speck receives his Phd, his dissertation is entitled "Theory and Engineering of Scheduling Parallel Jobs".
Ingo Müller receives his Phd, his dissertation is entitled "Engineering Aggregation Operators for Relational In-Memory Database Systems".
Moritz Kobitzsch receives his PhD, his dissertation is entitled "Alternative Route Techniques - and their Applications to the Stochastic on-time Arrival Problem".
Sascha Witt will receive one of two "Best Student Paper Awards" on ESA 2015 for his paper "Trip-Based Public Transit Routing".
Dr. Christian Schulz receives the KIT PhD award in the competence area "information, communication and organisation". The award ceremony took place on Februar 4, 2015.
receives the award as best graduate in the computer science department.
Dr. Christian Schulz receives the Uniserv research award for the best dissertation in the field of fast algorithms.
Dennis Schieferdecker receives his PhD, his dissertation is entitled "An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication".
receives his PhD, his dissertation is entitled "Time-Dependent Route Planning with Contraction Hierarchies".
The winter term 2013/14 course "Praxis der Softwareentwicklung" receives an award as best practical course during the graduation ceremony 'Tag der Informatik' on July 17, 2014.
Vitaly Osipov receives his PhD, his dissertation is entitled "Algorithm Engineering for Fundamental Sorting and Graph Problems".
Christian Schulz receives his PhD, his dissertation is entitled "High Quality Graph Partitioning".
Dennis Luxen receives his PhD, his dissertation is entitled "Building Blocks for Mapping Services".
Prof. Dr. Peter Sanders receives the Landesforschungspreis Baden-Württemberg 2011 (German only) in Applied Sciences.
Prof. Dr. Peter Sanders receives the DFG Gottfried Wilhelm Leibniz Award 2012 in Berlin.
Dr. Robert Geisberger receives the award of the Fördervereins des Forschungszentrums Informatik FZI for his dissertation "Advanced Route Planning in Transportation Networks" (2011).
- 02/02/2012: Prof. Dr. Peter Sanders, Prof. Dr. Dorothea Wagner and Prof. Dr. Hannah Bast (University of Freiburg) received the Google Focused Research Award with a research budget of 1 million dollars.
Prof. Dr. Peter Sanders is going to receive DFG's prestigious Gottfried Wilhelm Leibniz Award 2012 that consists of 2,5 million Euros in research funding. For further informations please see the KIT and the DFG press release.
receives his PhD, his dissertation is entitled "Efficient Algorithms for Large-Scale Image Analysis".
A paper of the group was accepted for the European Symposium on Algorithms 2011 (ESA): (Sanders, Schulz).
Award "365 Orte im Land der Ideen" 2011: Peter Sanders and Johannes Singler with Andreas Beckmann and Ulrich Meyer from the University of Frankfurt). Please see further information here.
Robert Geisberger receives his PhD, his dissertation is entitled 'Advanced Route Planning for Transportation Networks'.
- 07/27/2010: Two papers were accepted for the 17th String Processing and Information Retrieval Symposium (Spire 2010): Fischer et al. and Luxen et al.
Prof. Dr. Peter Sanders is going to receive DFG's prestigious Gottfried Wilhelm Leibniz Award 2012 that consists of 2,5 million Euros in research funding. For further informations please see the KIT and the DFG press release (both German only at this point).
- 07/12/2010: Two papers were accepted for the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010): Geisberger, Sanders and Geisberger, Luxen et al.
- 07/09/2010: After the final Sort Benchmark deadline for 2010, results from the group lead three subcategories of JouleSort, they are tied for the lead in one more. These results will also be presented at the Elektronik ecodesign congress.
Johannes Singler receives his PhD, his dissertation is entitled 'Algorithm Libraries for Multi-Core Processors'.
- 06/30/2010: A paper from the group was accepted, for the Conference on Artificial Intelligence and Interactive Digital Entertainment 2010 (AIIDE) (Geisberger, Sturtevant).
- 06/07/2010: Three papers from the group were accepted, for the European Symposium on Algorithms 2010 (ESA) (Osipov, Sanders) and (Geisberger et.al), and for ALGOSENSORS 2010 (Sanders, Schieferdecker).
- 05/26/2010: Two papers from the group were accepted, for the Symposium on Combinatorial Search (Geisberger, Schieferdecker) and for the International Green Computing Conference (Sanders, Singler et al.).
The second order for Prof. Sanders' book for the Algorithmen I (German only) lecture was sent to Springer today.
Change of dates: The oral examinations in Algorithmen I are not going to take place on April 4, 2010, but on April 27, starting at 9 a.m.
According to Springer, Prof. Sanders' book "Data Structures and Algorithms - The Basic Toolbox" for the Algorithmen I lecture will be delivered in week 16.
Members of the group, in cooperation with colleagues from Frankfurt, set new worls records in sorting large data energy-efficiently. Please see the press release.
The order for Prof. Sanders' book "Data Structures and Algorithms - The Basic Toolbox" for the lecture Algorithmen I (German only) was sent to Springer today. According to Springer, the books will be delivered in the week after Easter.
The group will present three papers at the Symposium on Experimental Algorithms (SEA'10) in Ischia, Italy. (Batz et al., Geisberger, Luxen et al.)
The written Algorithmen I exam takes place on March 8, 2010, 9 a.m., in the Hörsaal am Fasanengarten (Building 50.35). Please bring your student ID and one DIN A4 sheet of paper with your handwritten notes.
The group homepage now features the new KIT design. We apologize in advance for any inconvenience.
Frederik Transier received his PhD, his dissertation is entitled 'Algorithms and Data Structures for In-Memory Text Search Engines':
Prof. Dr. Peter Sanders was invited speaker at the ALENEX 2010 workshop, two of his group's papers (Singler et al., Geisberger et al.) were accepted there as well.
- November 2009
Interview with Dr. Dominik Schultes in the November edition of the KIT-Alumni-Newsletter.
Dr. Dominik Schultes receives the KIT-Doktorandenpreis 2009.
Dr. Dominik Schultes receives the Klaus-Tschira-Preis für verständliche Wissenschaft KlartText! which is awarded yearly for exceptional PhD-theses in biology, chemistry, computer science, mathematics, neurosciences and physics. The awardees present their theses in a special edition of the magazine "Bild der Wissenschaft".
Robert Geisberger finished his studies as the best graduate of the class of 2008/2009 and is honored at the Tag der Informatik 2009 (annual celebration of the faculty of computer sciences).
Prof. Dr. Peter Sanders, Johannes Singler, Dr. Mirko Rahn and Tim Kieritz win in two categories of the SortBenchmark 2009 competition, Indy Gray und Indy Minute (Press Release of the KIT).
According to Springer, "Data Structures and Algorithms - The Basic Toolbox" is being delivered at the moment.
The copies of "Data Structures and Algorithms - The Basic Toolbox" ordered on March 17, 2009, will be delivered between April 27 and 30, 2009. Until further notice there will not be another order.
The slides for the course "Algorithmen I" are now available.
Dr. Dominik Schultes received the award of the Förderverein des Forschungszentrums Informatik FZI for his dissertation "Route Planning in Road Networks" (2008).
- 9/15 to 9/19/2008
The ALGO 2008, one of the most important conferences in algorithmics which is held in a different country every year with varying workshops, took place in Karlsruhe, organized by the groups of Prof. Dr. Dorothea Wagner and Prof. Dr. Peter Sanders. 270 scientists from 23 countries attended the following workshops:
- 16th Annual European Symposium on Algorithms (ESA)
- 8th Workshop on Algorithms in Bioinformatics (WABI)
- 6th Workshop on Approximation and Online Algorithms (WAOA)
- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS)
- PhD meeting of the DFG priority program SPP 1307 "Algorithm Engineering".
Five internationally renowned scientists were invited to give talks: Prof. Dr. Rolf Möhring (Technische Universität Berlin), Prof. Dr. Mark Overmars (Utrecht University), Prof. Dr. Eytan Ruppin (Tel Aviv University), Prof. Dr. Leslie Valiant (Harvard University) and Prof. Dr. David Williamson (Cornell University). Due to the high scientific quality and the smooth organization the ALGO 2008 was a great success.
For their research in route planning, Prof. Dr. Peter Sanders and Dr. Dominik Schultes received the Research Award 2008, which comes with 90 000 USD prize money (press statement of the Universität Karlsruhe).
- May 2008
Prof. Dr. Peter Sanders' and Prof. Dr. Kurt Mehlhorns book "Data Structures and Algorithms - The Basic Toolbox" is published by Springer.
- April 2008
The "Taschenbuch der Algorithmen" is published, the chapter "Kürzeste Wege" was written by Prof. Dr. Peter Sanders and Johannes Singler.
Dominik Schultes received the Scientific American 50 Award 2007 in the category "The fastest way to get there".
- 12/3 to 12/5/2007
At the very first colloquium of the new DFG priority program "Algorithm Engineering" 73 scientists from all over Germany introduced the 21 projects chosen for the program. Invited talks were presented by Dr. Lutz Kettner (Berlin) and Prof. Dr. Giuseppe Italiano (University of Rome "La sapienza") and the event was organized by the group of Prof. Dr. Peter Sanders, who is the coordinator of the priority program.
- 9/30 to 10/01/2007
The paper "Full Bandwidth Broadcast, Reduction and Scan with only two Trees" by Prof. Dr. Peter Sanders, Jochen Speck and Jesper Larsson Träff was chosen "Outstanding Paper"at the EuroPVM/MPI User's Group Meeting 2007.
- 07/27/2010: Two papers were accepted for the 17th String Processing and Information Retrieval Symposium (Spire 2010): Fischer et al. and Luxen et al.