research
∙
07/04/2023
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
It is known that first-order logic with some counting extensions can be ...
share
research
∙
05/03/2023
Approximate Evaluation of Quantitative Second Order Queries
Courcelle's theorem and its adaptations to cliquewidth have shaped the f...
research
∙
04/24/2023
Pseudorandom Finite Models
We study pseudorandomness and pseudorandom generators from the perspecti...
research
∙
02/07/2023
First-Order Model Checking on Structurally Sparse Graph Classes
A class of graphs is structurally nowhere dense if it can be constructed...
research
∙
06/29/2022
Combinatorial and Algorithmic Aspects of Monadic Stability
Nowhere dense classes of graphs are classes of sparse graphs with rich s...
research
∙
06/28/2022
Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes
An indiscernible sequence (a̅_i)_1≤ i≤ n in a structure is an ordered se...
research
∙
02/27/2022
A logic-based algorithmic meta-theorem for mim-width
We introduce a logic called distance neighborhood logic with acyclicity ...
research
∙
02/25/2022
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
We present a fixed-parameter tractable algorithm for first-order model c...
research
∙
02/16/2022
SAT Backdoors: Depth Beats Size
For several decades, much effort has been put into identifying classes o...
research
∙
01/26/2022
Treelike decompositions for transductions of sparse graphs
We give new decomposition theorems for classes of graphs that can be tra...
research
∙
04/21/2021
Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes
The concept of bounded expansion provides a robust way to capture sparse...
research
∙
10/28/2020
Approximate Evaluation of First-Order Counting Queries
Kuske and Schweikardt introduced the very expressive first-order countin...
research
∙
06/25/2020
First-Order Model-Checking in Random Graphs and Complex Networks
Complex networks are everywhere. They appear for example in the form of ...
research
∙
05/04/2020
Advice for Online Knapsack With Removable Items
In the proportional knapsack problem, we are given a knapsack of some ca...
research
∙
10/01/2019
The Complexity of Packing Edge-Disjoint Paths
We introduce and study the complexity of Path Packing. Given a graph G a...
research
∙
03/29/2018
The Fine Structure of Preferential Attachment Graphs I: Somewhere-Denseness
Preferential attachment graphs are random graphs designed to mimic prope...
research
∙
09/26/2017