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).
AG Theoretische Informatik
Faculty 3 - Mathematics and Computer Science
Prof. Dr. Sebastian Siebertz
Telefon: +49 (0) 421 218 64450
- Summer 2021
- Winter 2020/21
- Algorithmentheorie (03-BE-699.11 (03-IBGT-AT)) ECTS: 6
- Set Theory and Model Theory (03-IMAT-STMT) ECTS: 6
- Bachelorprojekt: Parametrisierte Algorithmen auf Graphen
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:
- Édouard Bonnet et al., Twin-width and permutations
- Sebastian Siebertz and Alexandre Vigny, Parameterized Distributed Complexity Theory: A logical approach
- Nikolas Mählmann, Sebastian Siebertz and Alexandre Vigny, Recursive Backdoors for SAT
28.01.2021. Our paper on distributed domination was accepted at SIRROCCO 2021: arxiv.org/pdf/2012.02701.pdf
In the upcoming semester we will offer the lectures and seminars
- Theoretische Informatik 2 (03-BA-601.02, 03-IBGT-THI1, Sebastian Siebertz und Mario Grobler)
- Parametrisierte Komplexität (03-ME-602.22, 03-IMAT-PK, Sebastian Siebertz und Nikolas Mählmann)
- Databases, graphs and algorithms (03-IMVT-DGA, Alexandre Vigny)
- Seminar Parameterized Complexity (Sebastian Siebertz, Alexandre Vigny, Mario Grobler, Nikolas Mählmann)
12.01.2021 Upcoming Talk: Sebastian Siebertz will speak at SODA 2021 on January 12
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
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
- 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".
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