Research Area "Algorithmic and Formal Foundations"
Algorithms are structured sequences of instructions that solve tasks. Computer science strives to develop effective algorithms for certain problems, which make do with minimal instructions and resources. A central question is under which conditions problems can be solved algorithmically at all. A special area of computer science is non-numerical information processing, which is based on formal logic mechanisms and developed from computational perspectives.
Exemplary research topics include the following:
- Analysis of problems with respect to their algorithmic complexity
- Discovery of efficient algorithms for concrete problems, for example by following natural phenomena (computational intelligence) or combination of efficient algorithms for subproblems to cope with complex challenges (algorithm engineering)
- Estimation of the complexity of algorithms, for example the number of instructions to be executed
- Experimental investigation of algorithms
- Evaluation of heuristic and exact algorithms based on real application problems
Current research results
- Tom J. Ameloot, Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick: Reasoning on data partitioning for single-round multi-join evaluation in massively parallel systems. Commun. ACM 60(3): 93-100 (2017). DOI: 10.1145/3041063
- Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume: Reachability Is in DynFO. J. ACM 65(5): 33:1-33:24 (2018). DOI: 10.1145/3212685
- Mark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard J. Woeginger:
Fine-grained Complexity Analysis of Two Classic TSP Variants. ACM Trans. Algorithms 17(1): 5:1-5:29 (2021). DOI: 10.1145/3414845 - Jonas Ellert, Johannes Fischer: Linear Time Runs Over General Ordered Alphabets. ICALP 2021: 63:1-63:16. DOI: 10.4230/LIPIcs.ICALP.2021.63