412 citations · 423 across the 12 of their papers we have counts for
23 papers
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
Jan Dreier, Daniel Mock, Peter Rossmanith
It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth- minors have constant density.…
Pseudorandom Finite Models
Jan Dreier, Jamie Tucker-Foltz
We study pseudorandomness and pseudorandom generators from the perspective of logical definability. Building on results from ordinary derandomization and finite model theory, we sh…
First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly general…
Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad +2
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Mon…
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz +1
Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attent…
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský +4
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpret…
SAT Backdoors: Depth Beats Size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time t…
A logic-based algorithmic meta-theorem for mim-width
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ( for short) which extends existential with…
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…
Twin-width and generalized coloring numbers
Jan Dreier, Jakub Gajarsky, Yiting Jiang +2
In this paper, we prove that a graph with no -subgraph and twin-width has -admissibility and -coloring numbers bounded from above by an exponential function…
Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
Jan Dreier
The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order…
Approximate Evaluation of First-Order Counting Queries
Jan Dreier, Peter Rossmanith
Kuske and Schweikardt introduced the very expressive first-order counting logic FOC(P) to model database queries with counting operations. They showed that there is an efficient mo…
First-Order Model-Checking in Random Graphs and Complex Networks
Jan Dreier, Philipp Kuinke, Peter Rossmanith
Complex networks are everywhere. They appear for example in the form of biological networks, social networks, or computer networks and have been studied extensively. Efficient algo…
A Faster Cryptographer's Conspiracy Santa
Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas +1
In Conspiracy Santa, a variant of Secret Santa, a group of people offer each other Christmas gifts, where each member of the group receives a gift from the other members of the gro…
Optimal Threshold Padlock Systems
Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade +1
In 1968, Liu described the problem of securing documents in a shared secret project. In an example, at least six out of eleven participating scientists need to be present to open t…
The Complexity of Packing Edge-Disjoint Paths
Jan Dreier, Janosch Fuchs, Tim A. Hartmann +4
We introduce and study the complexity of Path Packing. Given a graph and a list of paths, the task is to embed the paths edge-disjoint in . This generalizes the well known H…
A Formal Analysis of 5G Authentication
David Basin, Jannik Dreier, Lucca Hirschi +3
Mobile communication networks connect much of the world's population. The security of users' calls, SMSs, and mobile data depends on the guarantees provided by the Authenticated Ke…
The Fine Structure of Preferential Attachment Graphs I: Somewhere-Denseness
Jan Dreier, Philipp Kuinke, Peter Rossmanith
Preferential attachment graphs are random graphs designed to mimic properties of typical real world networks. They are constructed by a random process that iteratively adds vertice…
Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application
Jan Dreier, Philipp Kuinke, Ba Le Xuan +1
We analyze some local properties of sparse Erdos-Renyi graphs, where is the edge probability. In particular we study the behavior of very short paths. For …
Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen
Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas +1
Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a g…
Overlapping Communities in Social Networks
Jan Dreier, Philipp Kuinke, Rafael Przybylski +3
Complex networks can be typically broken down into groups or modules. Discovering this "community structure" is an important step in studying the large-scale structure of networks.…
Overlapping Communities in Complex Networks
Jan Dreier
Communities are subsets of a network that are densely connected inside and share only few connections to the rest of the network. The aim of this research is the development and ev…
Brandt's Fully Private Auction Protocol Revisited
Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade
Auctions have a long history, having been recorded as early as 500 B.C. Nowadays, electronic auctions have been a great success and are increasingly used. Many cryptographic protoc…