412 citations · 423 across the 12 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.LO2023
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.…
cs.LO2023
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…
cs.LO2023★ 2 cited
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…