Publications (108)
The Surprising Power of Graph Neural Networks with Random Node Initialization
Ralph Abboud, Ä°smail Ä°lkan Ceylan, Martin Grohe +1
Graph neural networks (GNNs) are effective models for representation learning on relational data. However, standard GNNs are limited in their expressive power, as they cannot disti…
Testing Graph Isomorphism in Parallel by Playing a Game
Martin Grohe, Oleg Verbitsky
Our starting point is the observation that if graphs in a class C have low descriptive complexity in first order logic, then the isomorphism problem for C is solvable by a fast par…
Database Repairing with Soft Functional Dependencies
Nofar Carmeli, Martin Grohe, Benny Kimelfeld +2
A common interpretation of soft constraints penalizes the database for every violation of every constraint, where the penalty is the cost (weight) of the constraint. A computationa…
Physical Pooling Functions in Graph Neural Networks for Molecular Property Prediction
Artur M. Schweidtmann, Jan G. Rittig, Jana M. Weber +4
Graph neural networks (GNNs) are emerging in chemical engineering for the end-to-end learning of physicochemical properties based on molecular graphs. A key element of GNNs is the…
Counting Homomorphisms and Partition Functions
Martin Grohe, Marc Thurley
Homomorphisms between relational structures are not only fundamental mathematical objects, but are also of great importance in an applied computational context. Indeed, constraint…
Weisfeiler and Leman go Machine Learning: The Story so far
Christopher Morris, Yaron Lipman, Haggai Maron +5
In recent years, algorithms and neural architectures based on the Weisfeiler--Leman algorithm, a well-known heuristic for the graph isomorphism problem, have emerged as a powerful…
WL meet VC
Christopher Morris, Floris Geerts, Jan Tönshoff +1
Recently, many works studied the expressive power of graph neural networks (GNNs) by linking it to the -dimensional Weisfeiler--Leman algorithm (). Here, t…
Learning first-order definable concepts over structures of small degree
Martin Grohe, Martin Ritzert
We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of a logic over some background structure. We show that within this f…
Deciding first-order properties of nowhere dense graphs
Martin Grohe, Stephan Kreutzer, Sebastian Siebertz
Nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all clas…
Fixed-parameter tractability, definability, and model checking
Joerg Flum, Martin Grohe
In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized m…
Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf +1
We propose CRaWl, a novel neural network architecture for graph learning. Like graph neural networks, CRaWl layers update node features on a graph and thus can freely be combined o…
Finding topological subgraphs is fixed-parameter tractable
Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx +1
We show that for every fixed undirected graph , there is a time algorithm that tests, given a graph , if contains as a topological subgraph (that is, a…
Some Might Say All You Need Is Sum
Eran Rosenbluth, Jan Toenshoff, Martin Grohe
The expressivity of Graph Neural Networks (GNNs) is dependent on the aggregation functions they employ. Theoretical works have pointed towards Sum aggregation GNNs subsuming every…
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Anatole Dahan, Martin Grohe, Daniel Neuen +1
We present an additive -approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension running in time $n^{O(d/\varepsilon^{2})}…
word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
Martin Grohe
Vector representations of graphs and relational structures, whether hand-crafted feature vectors or learned representations, enable us to apply standard data analysis and machine l…
The Complexity of Datalog on Linear Orders
Martin Grohe, Goetz Schwandtner
We study the program complexity of datalog on both finite and infinite linear orders. Our main result states that on all linear orders with at least two elements, the nonemptiness…
Deep Weisfeiler Leman
Martin Grohe, Pascal Schweitzer, Daniel Wiebking
We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL), which allows the design of purely combinatorial graph isomorphism tests that are more powerful than the wel…
Computing with Tangles
Martin Grohe, Pascal Schweitzer
Tangles of graphs have been introduced by Robertson and Seymour in the context of their graph minor theory. Tangles may be viewed as describing "k-connected components" of a graph…
Generative Datalog with Continuous Distributions
Martin Grohe, Benjamin Lucien Kaminski, Joost-Pieter Katoen +1
Arguing for the need to combine declarative and probabilistic programming, Bárány et al. (TODS 2017) recently introduced a probabilistic extension of Datalog as a "purely declara…
Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth +1
The recent Long-Range Graph Benchmark (LRGB, Dwivedi et al. 2022) introduced a set of graph learning tasks strongly dependent on long-range interaction between vertices. Empirical…
Future Directions in the Theory of Graph Machine Learning
Christopher Morris, Fabrizio Frasca, Nadav Dym +7
Machine learning on graphs, especially using graph neural networks (GNNs), has seen a surge in interest due to the wide availability of graph data across a broad spectrum of discip…
Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles)
Martin Grohe
We survey an abstract theory of connectivity, based on symmetric submodular set functions. We start by developing Robertson and Seymour's fundamental duality between branch decompo…
Tuple-Independent Representations of Infinite Probabilistic Databases
Nofar Carmeli, Martin Grohe, Peter Lindner +1
Probabilistic databases (PDBs) are probability spaces over database instances. They provide a framework for handling uncertainty in databases, as occurs due to data integration, no…
Randomized Computations on Large Data Sets: Tight Lower Bounds
Martin Grohe, Andre Hernich, Nicole Schweikardt
We study the randomized version of a computation model (introduced by Grohe, Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that restricts random access to exte…
Local tree-width, excluded minors, and approximation algorithms
Martin Grohe
The local tree-width of a graph G=(V,E) is the function ltw^G: N -> N that associates with every natural number r the maximal tree-width of an r-neighborhood in G. Our main graph t…
Simulating Logspace-Recursion with Logarithmic Quantifier Depth
Steffen van Bergerem, Martin Grohe, Sandra Kiefer +1
The fixed-point logic LREC= was developed by Grohe et al. (CSL 2011) in the quest for a logic to capture all problems decidable in logarithmic space. It extends FO+C, first-order l…
The Complexity of Homomorphism Reconstruction Revisited
Timo Gervens, Martin Grohe, Louis Härtel +1
We revisit the algorithmic problem of reconstructing a graph from homomorphism counts that has first been studied in (Böker et al., STACS 2024): given graphs and…
Tight Lower Bounds for Query Processing on Streaming and External Memory Data
Martin Grohe, Christoph Koch, Nicole Schweikardt
We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is…
Molecular Machine Learning in Chemical Process Design
Jan G. Rittig, Manuel Dahmen, Martin Grohe +2
We present a perspective on molecular machine learning (ML) in the field of chemical process engineering. Recently, molecular ML has demonstrated great potential in (i) providing h…
Graph Similarity and Approximate Isomorphism
Martin Grohe, Gaurav Rattan, Gerhard J. Woeginger
The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not rec…
Constraint Solving via Fractional Edge Covers
Martin Grohe, Dániel Marx
Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence identifying polynomial-time solvable classes of constraint satisfaction problems has…
The Hardness of Embedding Grids and Walls
Yijia Chen, Martin Grohe, Bingkai Lin
The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph from some class of "pattern graphs" can be embedd…
Probabilistic Query Evaluation with Bag Semantics
Martin Grohe, Peter Lindner, Christoph Standke
We study the complexity of evaluating queries on probabilistic databases under bag semantics. We focus on self-join free conjunctive queries, and probabilistic databases where occu…
A complexity dichotomy for partition functions with mixed signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum +1
Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the nu…
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…
Query Languages for Machine-Learning Models
Martin Grohe
In this paper, I discuss two logics for weighted finite structures: first-order logic with summation (FO(SUM)) and its recursive extension IFP(SUM). These logics originate from fou…
Query languages for neural networks
Martin Grohe, Christoph Standke, Juno Steegmans +1
We lay the foundations for a database-inspired approach to interpreting and understanding neural network models by querying them using declarative languages. Towards this end we st…
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
Martin Grohe, Sandra Kiefer
The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial procedure for detecting symmetries in graphs and it is widely used in graph-isomorphism tests. It proceeds by iter…
Infinite Probabilistic Databases
Martin Grohe, Peter Lindner
Probabilistic databases (PDBs) are used to model uncertainty in data in a quantitative way. In the standard formal framework, PDBs are finite probability spaces over relational dat…
On the Parameterized Complexity of Learning First-Order Logic
Steffen van Bergerem, Martin Grohe, Martin Ritzert
We analyse the complexity of learning first-order queries in a model-theoretic framework for supervised learning introduced by (Grohe and Turán, TOCS 2004). Previous research on t…
Infinite Probabilistic Databases
Martin Grohe, Peter Lindner
Probabilistic databases (PDBs) model uncertainty in data in a quantitative way. In the established formal framework, probabilistic (relational) databases are finite probability spa…
Recursive querying of neural networks via weighted structures
Martin Grohe, Christoph Standke, Juno Steegmans +1
Expressive querying of machine learning models - viewed as a form of intentional data - enables their verification and interpretation using declarative languages, thereby making le…
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Christoph Berkholz, Paul Bonsma, Martin Grohe
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to f…
Are Targeted Messages More Effective?
Martin Grohe, Eran Rosenbluth
Graph neural networks (GNN) are deep learning architectures for graphs. Essentially, a GNN is a distributed message passing algorithm, which is controlled by parameters learned fro…
Order Invariance on Decomposable Structures
Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe
Order-invariant formulas access an ordering on a structure's universe, but the model relation is independent of the used ordering. Order invariance is frequently used for logic-bas…
A Faster Isomorphism Test for Graphs of Small Degree
Martin Grohe, Daniel Neuen, Pascal Schweitzer
In a recent breakthrough, Babai (STOC 2016) gave a quasipolynomial time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our a…
Size bounds and query plans for relational joins
Albert Atserias, Martin Grohe, Dániel Marx
Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often domin…
Probabilistic Data with Continuous Distributions
Martin Grohe, Benjamin Lucien Kaminski, Joost-Pieter Katoen +1
Statistical models of real world data typically involve continuous probability distributions such as normal, Laplace, or exponential distributions. Such distributions are supported…
Isomorphism Testing for Graphs of Bounded Rank Width
Martin Grohe, Pascal Schweitzer
We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the clique width of a graph is bounded in terms of its ra…
Some Thoughts on Graph Similarity
Martin Grohe
We give an overview of different approaches to measuring the similarity of, or the distance between, two graphs, highlighting connections between these approaches. We also discuss…
A Finite-Model-Theoretic View on Propositional Proof Complexity
Erich Grädel, Martin Grohe, Benedikt Pago +1
We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory. Specifically, we show that the power of several propositional…
A Rank-Preserving Gaifman Normal Form
Martin Grohe, Nicole Schweikardt
We introduce a rank measure for first-order logic and prove a "rank-preserving'" version of Gaifman's theorem. Compared to earlier "rank-preserving locality theorems'" (in particul…
Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs
Jan Tönshoff, Martin Grohe
Boolean Satisfiability (SAT) solvers are foundational to computer science, yet their performance typically hinges on hand-crafted heuristics. This work introduces Reinforcement Lea…
Distinguished In Uniform: Self Attention Vs. Virtual Nodes
Eran Rosenbluth, Jan Tönshoff, Martin Ritzert +2
Graph Transformers (GTs) such as SAN and GPS are graph processing models that combine Message-Passing GNNs (MPGNNs) with global Self-Attention. They were shown to be universal func…
Where First-Order and Monadic Second-Order Logic Coincide
Michael Elberfeld, Martin Grohe, Till Tantau
We study on which classes of graphs first-order logic (FO) and monadic second-order logic (MSO) have the same expressive power. We show that for all classes C of graphs that are cl…
L-Recursion and a new Logic for Logarithmic Space
Martin Grohe, Berit GruÃien, André Hernich +1
We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic…
Monadic Datalog Containment on Trees
André Frochaux, Martin Grohe, Nicole Schweikardt
We show that the query containment problem for monadic datalog on finite unranked labeled trees can be solved in 2-fold exponential time when (a) considering unordered trees using…
The Descriptive Complexity of Graph Neural Networks
Martin Grohe
We analyse the power of graph neural networks (GNNs) in terms of Boolean circuit complexity and descriptive complexity. We prove that the graph queries that can be computed by a po…
Graph Similarity Based on Matrix Norms
Timo Gervens, Martin Grohe
Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the comput…
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…
Colouring and Covering Nowhere Dense Graphs
Martin Grohe, Stephan Kreutzer, Roman Rabinovich +2
It was shown by Grohe et al. that nowhere dense classes of graphs admit sparse neighbourhood covers of small degree. We show that a monotone graph class admits sparse neighbourhood…
Amortized Molecular Optimization via Group Relative Policy Optimization
Muhammad bin Javaid, Hasham Hussain, Ashima Khanna +5
In structurally constrained molecular optimization, state-of-the-art methods restart an expensive oracle-driven search from scratch for every new input structure, scaling poorly to…
The succinctness of first-order logic on linear orders
Martin Grohe, Nicole Schweikardt
Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be exp…
Enumerating Homomorphisms
Andrei A. Bulatov, Victor Dalmau, Martin Grohe +1
The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision ve…
The Importance of Parameters in Database Queries
Amir Gilad, Martin Grohe, Benny Kimelfeld +2
We propose and study a framework for quantifying the importance of the choices of parameter values to the result of a query over a database. These parameters occur as constants in…
GraphXForm: Graph transformer for computer-aided molecular design
Jonathan Pirnay, Jan G. Rittig, Alexander B. Wolf +4
Generative deep learning has become pivotal in molecular design for drug discovery, materials science, and chemical engineering. A widely used paradigm is to pretrain neural networ…
Structural Node Embeddings with Homomorphism Counts
Hinrikus Wolf, Luca Oeljeklaus, Pascal Kühner +1
Graph homomorphism counts, first explored by Lovász in 1967, have recently garnered interest as a powerful tool in graph-based machine learning. Grohe (PODS 2020) proposed the the…
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…
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
Martin Grohe, Sandra Kiefer
The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism te…
Learning MSO-definable hypotheses on string
Martin Grohe, Christof Löding, Martin Ritzert
We study the classification problems over string data for hypotheses specified by formulas of monadic second-order logic MSO. The goal is to design learning algorithms that run in…
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…
The Iteration Number of the Weisfeiler-Leman Algorithm
Martin Grohe, Moritz Lichter, Daniel Neuen
We prove new upper and lower bounds on the number of iterations the -dimensional Weisfeiler-Leman algorithm (-WL) requires until stabilization. For , we show that $…
Isomorphism Testing for Graphs Excluding Small Minors
Martin Grohe, Daniel Neuen, Daniel Wiebking
We prove that there is a graph isomorphism test running in time on -vertex graphs excluding some -vertex graph as a minor. Previously known bo…
Dimension Reduction via Colour Refinement
Martin Grohe, Kristian Kersting, Martin Mladenov +1
Colour refinement is a basic algorithmic routine for graph isomorphism testing, appearing as a subroutine in almost all practical isomorphism solvers. It partitions the vertices of…
End-to-End Reinforcement Learning of Curative Curtailment with Partial Measurement Availability
Hinrikus Wolf, Luis Böttcher, Sarra Bouchkati +9
In the course of the energy transition, the expansion of generation and consumption will change, and many of these technologies, such as PV systems, electric cars and heat pumps, w…
Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit
Eran Rosenbluth, Martin Grohe
We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggreg…
The Logic of Graph Neural Networks
Martin Grohe
Graph neural networks (GNNs) are deep learning architectures for machine learning problems on graphs. It has recently been shown that the expressiveness of GNNs can be characterise…
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
Martin Grohe, Dániel Marx
We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph as a minor to graphs excluding as a topological subgraph. We prove that for…
Canonisation and Definability for Graphs of Bounded Rank Width
Martin Grohe, Daniel Neuen
We prove that the combinatorial Weisfeiler-Leman algorithm of dimension is a complete isomorphism test for the class of all graphs of rank width at most . Rank width is…
Probabilistic Databases with an Infinite Open-World Assumption
Martin Grohe, Peter Lindner
Probabilistic databases (PDBs) introduce uncertainty into relational databases by specifying probabilities for several possible instances. Traditionally, they are finite probabilit…
Definable decompositions for graphs of bounded linear cliquewidth
MikoÅaj BojaÅczyk, Martin Grohe, MichaÅ Pilipczuk
We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth de…
Graph Neural Networks for Maximum Constraint Satisfaction
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf +1
Many combinatorial optimization problems can be phrased in the language of constraint satisfaction problems. We introduce a graph neural network architecture for solving such optim…
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…
Graph Machine Learning for Design of High-Octane Fuels
Jan G. Rittig, Martin Ritzert, Artur M. Schweidtmann +7
Fuels with high-knock resistance enable modern spark-ignition engines to achieve high efficiency and thus low CO2 emissions. Identification of molecules with desired autoignition p…
Tangles and Connectivity in Graphs
Martin Grohe
This paper is a short introduction to the theory of tangles, both in graphs and general connectivity systems. An emphasis is put on the correspondence between tangles of order k an…
Recent Advances on the Graph Isomorphism Problem
Martin Grohe, Daniel Neuen
We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test and subsequent developments that l…
Model-Checking Problems as a Basis for Parameterized Intractability
Joerg Flum, Martin Grohe
Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For exa…
Stable Tuple Embeddings for Dynamic Databases
Jan Toenshoff, Neta Friedman, Martin Grohe +1
We study the problem of computing an embedding of the tuples of a relational database in a manner that is extensible to dynamic changes of the database. In this problem, the embedd…
How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Arie Soeteman, Michael Benedikt, Martin Grohe +1
Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data, based on local aggregation over neighbors. GNNs have close connections to…
Quasi-4-Connected Components
Martin Grohe
We introduce a new decomposition of a graphs into quasi-4-connected components, where we call a graph quasi-4-connected if it is 3-connected and it only has separations of order 3…
One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction
Jan Tönshoff, Berke Kisin, Jakob Lindner +1
We propose a universal Graph Neural Network architecture which can be trained as an end-2-end search heuristic for any Constraint Satisfaction Problem (CSP). Our architecture can b…
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
Christoph Berkholz, Martin Grohe
In recent years, we have seen several approaches to the graph isomorphism problem based on "generic" mathematical programming or algebraic (Gröbner basis) techniques. For most of…
Lovász Meets Weisfeiler and Leman
Holger Dell, Martin Grohe, Gaurav Rattan
In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensi…
An improved isomorphism test for bounded-tree-width graphs
Martin Grohe, Daniel Neuen, Pascal Schweitzer +1
We give a new fpt algorithm testing isomorphism of -vertex graphs of tree width in time , improving the fpt algorithm…
Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs
Martin Grohe
The question of whether there is a logic that captures polynomial time was formulated by Yuri Gurevich in 1988. It is still wide open and regarded as one of the main open problems…
Limitations of Algebraic Approaches to Graph Isomorphism Testing
Christoph Berkholz, Martin Grohe
We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Gröbner basis computation. The idea of these algorithms is to encode two grap…
Independence in Infinite Probabilistic Databases
Martin Grohe, Peter Lindner
Probabilistic databases (PDBs) model uncertainty in data. The current standard is to view PDBs as finite probability spaces over relational database instances. Since many attribute…
Deciding first-order properties of locally tree-decomposable structures
Markus Frick, Martin Grohe
We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable c…
Randomisation and Derandomisation in Descriptive Complexity Theory
Kord Eickmeyer, Martin Grohe
We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic…
Computing Crossing Numbers in Quadratic Time
Martin Grohe
We show that for every fixed non-negative integer k there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, c…