Skip to main content

AG Theoretische Informatik

Our research group focuses on the design of efficient algorithms for graph problems. Many important problems are hard to solve in general, hence we try to identify the most general graph classes on which tractability can be achieved. We are also interested in logical methods in computer science. One problem of particular interest is the model-checking problem for first-order logic. In this context we currently study logically defined graph classes, inspired by classical model theory (stability theory).

Contact

AG Theoretische Informatik
Faculty 3 - Mathematics and Computer Science
Prof. Dr. Sebastian Siebertz

Bibliothekstr. 5
28359 Bremen

Secretary office
Tanja Rethemeyer
Telefon: +49 (0) 421 218 64450

Wordcloud

Research topics

Structural Graph Theory, in particular the theory of sparse and structurally sparse graphs.

Parameterized Complexity Theory

Logic in Computer Science, in particular first-order model-checking, query evaluation, enumeration, and counting.

Applications of stability theory in the finite.

Aufmerksame Zuhörer in einem Seminarraum.

Teaching

News

17.02.2021 Upcoming Talk: Patrice Ossona de Mendez will speak in our seminar about First-order transductions of graphs on February 17, 9:00 am.

13.02.2021. We submitted three papers to ICALP 2021: 

28.01.2021. Our paper on distributed domination was accepted at SIRROCCO 2021: arxiv.org/pdf/2012.02701.pdf

20.01.2021 Upcoming Talk: Éduard Bonnet will speak in our seminar about Twinwidth on 20.01 9:00.

Titel: Twinwidth. Zoom link

12.01.2021 Upcoming Talk: Sebastian Siebertz will speak at SODA 2021 on January 12

meetings.siam.org/program.cfm

15.12.2020. Sebastian Siebertz was a speaker at IPEC 2020: arxiv.org/pdf/1910.00581.pdf

4.12.2020. We submitted a paper based on the bachelor thesis of Simeon Kublenz to SIRROCCO 2021: arxiv.org/pdf/2012.02701.pdf

5.11.2020, Mario Grobler (University of Bremen) Parikh automata on finite and and infinite words

1.10.2020. Mario Grobler has joined the team as a PhD student. Welcome Mario!

10.09.2020. Sebastian Siebertz was a speaker in the IBS Virtual Discrete Math Colloquium dimag.ibs.re.kr/event/2020-09-10/

26.08.2020. Alexandre Vigny was a speaker at MFCS 2020: drops.dagstuhl.de/opus/volltexte/2020/12755/pdf/LIPIcs-MFCS-2020-65.pdf

In the upcoming winter semester we will offer the lectures

  • Set Theory and Model Theory
  • Algorithmentheorie

and the

  • Bachelorproject: Parametrisierte Algorithmen auf Graphen.

21.01.2020. Sebastian Siebertz presented his Antrittsvorlesung at the University of Bremen.

2.11.2019. Sebastian Siebertz was an invited speaker at WGT-Workshop on Graph Theory and Its Applications-IX in Istanbul

28.10.2019. Alexandre Vigny gave a presentation on Query enumeration and nowhere dense graphs in Berlin.

23.10.2019. Alexandre Vigny gave a presentation on Query enumeration and nowhere dense graphs in Bremen.

14.10.2019. The lectures have started. We are offering the Bachelor's course "Theoretische Informatik 1", a Master's course "Sparsity" and a Master's course "Finite and algorithmic model theory".

1.10.2019. Alexandre Vigny has joined the team as a postdoc. Welcome Alexandre!

26.9.2019. Sebastian Siebertz was a speaker at 29. Theorietag der Fachgruppe Automaten und Formale Sprache in Bremen.

15.09.2019. Sebastian Siebertz was an invited speaker at Highlights of Logic, Games and Automata in Warsaw