7 papers
First-Order Query Evaluation with Cardinality Conditions
Martin Grohe, Nicole Schweikardt
We study an extension of first-order logic that allows to express cardinality conditions in a similar way as SQL's COUNT operator. The corresponding logic FOC(P) was introduced by…
Isomorphism for Tournaments of Small Twin Width
Martin Grohe, Daniel Neuen
We prove that isomorphism of tournaments of twin width at most can be decided in time . This implies that the isomorphism problem for classes of tourname…
Automorphism groups of graphs of bounded Hadwiger number
Martin Grohe, Pascal Schweitzer, Daniel Wiebking
We determine the structure of automorphism groups of finite graphs of bounded Hadwiger number. Our proof includes a structural analysis of finite edge-transitive graphs. In particu…
Homomorphism Tensors and Linear Equations
Martin Grohe, Gaurav Rattan, Tim Seppelt
Lovász (1967) showed that two graphs and are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph , the…
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe, Moritz Lichter, Daniel Neuen +1
The -dimensional Weisfeiler-Leman (-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applic…
The Parameterized Complexity of Learning Monadic Second-Order Logic
Steffen van Bergerem, Martin Grohe, Nina Runde
Within the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in mon…