Foundations and Discrete Mathematics

The research area "Foundations and Discrete Mathematics" has its roots in the area "Foundations", existing since 2000 and previously coordinated by Seth Pettie, and the area "Discrete Mathematics", which was founded in 2005 and coordinated by Benjamin Doerr since then. After Seth Pettie took up a professorship in Michigan, U.S.A, in 2006, the two areas were joined to one. In 2008, its highly successful activities on bio-inspired computation became their own research area.

Coordinator

Benjamin Doerr

Researchers

Recent members

Research Area

Our focus is to investigate those structures and principles that are fundamental for the understanding and design of efficient algorithms. This includes combinatorial objects like graphs and hypergraphs, methods from probability theory, and classical computer science topics like complexity theory. Since these ingredients are crucial for many, also more applied problems, there is a rich exchange with the other research areas in AG1.

The particular topics we work on are subject to change, influenced both by people joining and leaving the group and by current developments in algorithmics. Topics that emerged or got a strongly increased attention in the last few years include random graphs, quasirandomness, and theoretical analyses of evolutionary algorithms (now an independent research area); classical topics are graph algorithms, data structures and complexity theory.

Complexity Theory: Understanding how difficult a problem is to be solved by a computer program is a classic topic in computer science. Recently active questions include parameterized complexity and black-box complexity.
Graph Theory and Algorithms: Graphs are a fundamental mathematical abstraction of the real-world phenomenon of being neighbors. They allow beautiful theory like Euler′s famous solution to the Königsberg Bridge problem and are the basis of many classical algorithmic problems like finding shortest paths or computing flows in networks.
Data Structures: Data structures are the backbone of algorithms. Sorting and string problems are some of the very basic problems. Although the basic questions have been answered, there are still many open problems in these areas which remain relevant in our days.

Sample Publications

K. Panagiotou, R. Spöhel, A. Steger, H. Thomas.
Explosive percolation in Erdős-Rényi-like graph processes. [link]
In Proceedings of EuroComb 2011, to appear.
D. Hermelin, A. Levy, O. Weimann, R. Yuster.
Distance oracles for vertex-labeled graphs. [link] [pdf]
In Proceedings of ICALP 2011, pages 490-501, 2011.
B. Doerr, C. Winzen.
Towards a complexity theory of randomized search heuristics: Ranking-based black-box complexity. [pdf (arxiv)] [link]
In Proceedings of 6th International Computer Science Symposium in Russia (CSR 2011), pages 15-28, 2011.
B. Doerr, M. Fouz, T. Friedrich.
Social networks spread rumors in sublogarithmic time. [link] [pdf]
In Proceedings of STOC 2011, pages 21-30, 2011.
B. Doerr, M. Künnemann, M. Wahlström.
Dependent randomized rounding: The bipartite case. [pdf]
In Proceedings of ALENEX 2011, pages 96-107.
N. Fountoulakis, M. Khosla, K. Panagiotou.
The multiple-orientability thresholds for random hypergraphs. [pdf]
In Proceedings of SODA 2011, pages 1222-1236.
B. Doerr, D. Johannsen, C. Winzen.
Multiplicative drift analysis. [link]
In Proceedings of GECCO 2010, pages 1449-1456.
S. Kratsch, M. Wahlström.
Preprocessing of Min Ones problems: A dichotomy. [link] [pdf]
In Proceedings of ICALP 2010, pages 653-665.
T. Friedrich, M. Gairing, T. Sauerwald.
Quasirandom load balancing. [pdf]
In Proceedings of SODA 2010, pages 1620-1629.
N. Garg, T. Kavitha, A. Kumar, K. Mehlhorn, J. Mestre.
Assigning papers to referees. [pdf]
In Algorithmica 58(1), pages 119-136, 2010.