Unifying Theories for Multivariate Algorithms

• Applicant: Professor Dr. Sebastian Siebertz
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 446200270

Studying the tractability of computational problems is a core challenge in theoretical computer science. A central question is when, why, and how computational problems can be solved efficiently. Towards answering this question, the theory of algorithms has offered powerful unifying results, called algorithmic meta-theorems (AMTs) that provide general mathematical conditions implying the automatic derivation of efficient algorithms. These conditions are typically linked to the descriptive complexity of the problems (via logic) and the structural properties of their inputs (via combinatorics). AMTs, while infrequent, are precious because they provide a deep understanding of the nature of computational tractability.This proposal aims at revealing the unification potential of AMTs in discrete algorithms. We are going to employ the framework of parameterized complexity theory, where algorithm efficiency is evaluated not only with respect to the input size but also with respect to additional key secondary parameters. This multivariate approach allows to flexibly take into account the logical and structural conditions that are typically encountered in problem parametrizations. Parameterized complexity theory is a fully developed discipline of theoretical computer science and has developed an extended arsenal of algorithmic techniques and paradigms. Their systematic elevation to AMTs is a mature and non-trivial challenge that calls for a qualitative shift in the theory of algorithms from the study of particular problems to the quest for unifying algorithmic theories.We plan to distill the best meta-algorithmic value from the most advanced techniques in all aspects of contemporary parameterized complexity theory. We propose the proof of AMTs for wide families of problems in diverse contexts in discrete algorithms. The ultimate outcome will be the establishment of AMTs as an essential unification ingredient of the theory of algorithms.

• DFG Programme: Research Grants
• International Connection: France
• Partner Organisation: Agence Nationale de la Recherche / The French National Research Agency
• Cooperation Partner: Professor Dr. Dimitrios Thilikos Touloupas