Nikolas Mählmann
About Me:
I am a 3rd year PhD-student in the
Theoretical Computer Science Group at the University of Bremen supervised by
Prof. Dr. Sebastian Siebertz.
My research interests lie in the intersection of structural graph theory, logic, and algorithms. Currently I am studying monadically stable and monadically NIP classes of graphs and structures. Originating in model theory,
those classes generalize many algorithmically tractable graph classes.
Together with my collaborators, in a series of papers [4-7], we developed a combinatorial structure theory for monadically stable graph classes and showed that the FO Model Checking problem is fixed parameter tractable on those classes.
Given a first-order logic sentence φ and a graph G, the goal is to
decide whether φ is true on G. Due to the flexibility of first-order logic, an efficient algorithm for this problem can be used to solve a multitude of graph problems.
My next goal is to extend our results to monadically NIP graph classes.
Contact me at: maehlmann[at]uni-bremen[dot]de
Publications:
[8] Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
accepted at STOC 2024 |
arXiv
[7] First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, Szymon Toruńczyk
[6] First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
[5] Flipper Games for Monadically Stable Graph Classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski, Szymon Toruńczyk
[4] Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Toruńczyk
[3] Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny
[2] Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk
[1] Recursive Backdoors for SAT
Nikolas Mählmann, Sebastian Siebertz, Alexandre Vigny
Visits:
[Nov 2023] MIMUW, University of Warsaw, Poland
Research topics: applications of flip-breakability in monadically NIP graph classes
[Mar - May 2023] MIMUW, University of Warsaw, Poland
Research topics: monadically stable and monadically NIP graph classes, model checking, flip-width
[Nov 2022] LIRMM, University of Montpellier, France
Research topics: minor-free graph classes
Talks:
Combinatorial Characterizations of Monadically Stable and Monadically NIP Graph Classes
Flip-Breakability: Combinatorial Characterizations of Monadically NIP Graph Classes
Flipper Games for Monadically Stable Graph Classes
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes
First-Order Model Checking on Structurally Sparse Graph Classes
Monadically Stable Classes of Graphs
Automata Theory Seminar at the University of Warsaw
Combinatorial and Algorithmic Aspects of Monadic Stability
Algorithmic Meta-Theorems
Invited lecture at Hanyang University
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Indiscernible Sequences in Monadically Stable and Monadically NIP Classes
Recursive Backdoors for SAT
Highlights of Logic, Games and Automata 2021 |
slides
Teaching:
I served as a TA in the following courses.
| Semester |
Course |
Type |
| WiSe 2023/24 |
Sparsity - Graphs and Algorithms |
Lecture |
| SoSe 2022 |
GRAPA: Parameterized Algorithms on Graphs (2/2) |
Students Project |
| WiSe 2021/22 |
GRAPA: Parameterized Algorithms on Graphs (1/2) |
Students Project |
| WiSe 2021/22 |
Algorithmentheorie (EN: Theory of Algorithms) |
Lecture |
| SoSe 2021 |
Parameterized Complexity |
Lecture |
(last updated: 2024.03.26)