Prof. Dr. Sebastian Siebertz

Prof. Dr. Sebastian Siebertz

Universität Bremen
FB3: Mathematik-Informatik
Bibliothekstr. 5
28359 Bremen
Germany

Office: MZH 3160
Phone: +49 (421) 218-63751
siebertz[at]uni-bremen[dot]de

Office hours: by appointment

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.

Current PhD students and Postdocs

Dr. Alexandre Vigny

Mario Grobler

Nikolas Mählmann

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

Curriculum Vitae

PDF-Download