Foundations of algorithmic stability theory

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

First-order and monadic second-order logic play important roles in computer science. Besides the traditional connections with finite automata and regular languages, descriptive complexity, and many more, they find strong applications in the formulation of algorithmic meta theorems. An algorithmic meta theorem provides algorithmic techniques that work not only for individual problems but for whole classes of problems. These classes of problems are often specified by logical means. A famous example of an algorithmic meta theorem is Courcelle's Theorem, stating that every property definable in monadic second-order logic can be decided in linear time on every class of graphs of bounded tree-width. A similar result for first-order logic statesthat every property definable in first-order logic can be decided in almost linear time on every nowhere dense class of graphs. Under standard complexity theoretic assumptions both of these tractability results cannot be extended to more general graph classes which are closed under taking subgraphs, hence, the classification of subgraph-closed graph classes on which monadic second-order and first-order properties can be decided efficiently is essentially complete.The goal of this project is to develop a systematic understanding of the combinatorial structure underlying algorithmic tractability beyond subgraph-closed graph classes. The main tool that will be applied is stability theory, also known as classification theory, which is one of the most successful areas of contemporary mathematical logic. Recent results successfully combine methods from discrete mathematics and stability theory to obtain strong structural and algorithmic results for important graph classes. Examples include efficient algorithms for nowhere dense graph classes, which are stable, a regularity lemma without exceptional pairs for stable graphs, and a definable regularity lemma for hypergraphs with the non-independence property (NIP), which is a model-theoretic counterpart of the Vapnik-Chervonenkis dimension. I aim to provide a rigorous foundational analysis of algorithmic applications of stability theory in finite combinatorics and graph theory. The immediate beneficiaries of this research will be researchers in theoretical computer science, especially in parameterized complexity and approximation algorithms, graph theory, and logic.

• DFG Programme: Research Grants