Prof. Dr. Sebastian Siebertz
Research Interests
- Algorithmic Graph Structure Theory, in particular the theory of sparse and structurally sparse grap.
- Logic in Computer Science, in particular first-order model-checking, query evaluation, enumeration, and counting.
- Applications of stability theory in the finite.
A large part of my research is concerned with the design of efficient algorithms for graph problems. Many important problems are hard to solve in general, hence I try to identify the most general graph classes on which tractability can be achieved. I have studied intensively the theory of bounded expansion and nowhere dense graph classes, which provide a very robust notion of uniform sparsity.
I am also interested in logical methods in computer science. One of my favourite problems is the model-checking problem for first-order logic. In collaboration with Martin Grohe and Stephan Kreutzer I proved that this problem is fixed-parameter tractable on nowhere dense graph classes. I am now trying to extend this result to more general graph classes, in particular to logically defined classes as studied in classical model theory (stability theory).
Publications
A complete list of my publications can be found on dblp.org
Talks
- Introduction to nowhere dense graphs. CSLOG Seminar, Bremen, 14.11.2019.
- On the generalised colouring numbers. WGT-Workshop on Graph Theory and Its Applications-IX, Istanbul, 02.11.2019.
- Structural Sparsity. 29. Theorietag der Fachgruppe Automaten und Formale Sprachen, Bremen, 26.9.2019.
- Nowhere dense graph classes and algorithmic applications. Highlights of Logic, Games and Automata,
Invited tutorial, 15.9.2019.
Service
Organization of
Dagstuhl seminar Sparsity in Algorithms, Combinatorics and Logic
Program committees
- FoSSaCS 2020
- MFCS 2020
- CSL 2018
- Highlights of Logics Games and Automata 2018
- LICS 2021
- IPEC 2021
- Hightlights 2021