Martin Grohe

Q: What Schools Are Affiliated With Martin Grohe

Martin Grohe is affiliated with the following schools: Humboldt University of Berlin, University of Freiburg, University of Edinburgh, RWTH Aachen University, Technical University of Berlin

Martin Grohe's AcademicInfluence.com Rankings

Martin Grohe

Computer Science

#3080

World Rank

#3230

Historical Rank

Theoretical Computer Science

#95

World Rank

#95

Historical Rank

Database

#1839

World Rank

#1928

Historical Rank

computer-science Degrees

Martin Grohe

Mathematics

#4445

World Rank

#6311

Historical Rank

Graph Theory

#81

World Rank

#89

Historical Rank

Measure Theory

#1513

World Rank

#1885

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Why Is Martin Grohe Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Martin Grohe is a German mathematician and computer scientist known for his research on parameterized complexity, mathematical logic, finite model theory, the logic of graphs, database theory, and descriptive complexity theory. He is a University Professor of Computer Science at RWTH Aachen University, where he holds the Chair for Logic and Theory of Discrete Systems.

(See a Problem?)

Martin Grohe's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Parameterized Complexity Theory (2006) (1914)
Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series) (2006) (1237)
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018) (887)
The complexity of homomorphism and constraint satisfaction problems seen from the other side (2003) (456)
The complexity of first-order and monadic second-order logic revisited (2002) (277)
Size Bounds and Query Plans for Relational Joins (2008) (251)
Query evaluation via tree-decompositions (2001) (247)
The parameterized complexity of counting problems (2002) (239)
Path Queries on Compressed XML (2003) (225)
Deciding first-order properties of locally tree-decomposable structures (2000) (218)
Deciding first-order properties of nowhere dense graphs (2013) (206)
Constraint solving via fractional edge covers (2014) (176)
The complexity of partition functions (2005) (167)
Local Tree-Width, Excluded Minors, and Approximation Algorithms (2000) (162)
When is the evaluation of conjunctive queries tractable? (2001) (141)
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory (2017) (132)
Locally Excluding a Minor (2007) (123)
Fixed-Parameter Tractability, Definability, and Model-Checking (1999) (121)
Finding topological subgraphs is fixed-parameter tractable (2010) (121)
Structure theorem and isomorphism test for graphs with excluded topological subgraphs (2011) (110)
Computing crossing numbers in quadratic time (2000) (106)
A Complexity Dichotomy for Partition Functions with Mixed Signs (2008) (106)
Describing parameterized complexity classes (2002) (105)
Hypertree width and related hypergraph invariants (2007) (105)
Logic, graphs, and algorithms (2007) (103)
The Surprising Power of Graph Neural Networks with Random Node Initialization (2020) (96)
Hypertree Decompositions: Structure, Algorithms, and Applications (2005) (92)
Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors (2010) (89)
Query evaluation on compressed trees (2003) (89)
On tree width, bramble size, and expansion (2009) (87)
Fixed-point logics on planar graphs (1998) (85)
On Parameterized Approximability (2006) (84)
word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data (2020) (77)
Definability and Descriptive Complexity on Databases of Bounded Tree-Width (1999) (75)
Methods for Algorithmic Meta Theorems (2009) (75)
Non-dichotomies in Constraint Satisfaction Complexity (2008) (75)
Model Theoretic Methods in Finite Combinatorics (2011) (71)
PEBBLE GAMES AND LINEAR EQUATIONS (2012) (70)
Computing excluded minors (2008) (70)
Isomorphism testing for embeddable graphs through definability (2000) (66)
Algorithmic Meta Theorems (2008) (66)
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement (2013) (65)
Locality of order-invariant first-order formulas (1998) (61)
Colouring and Covering Nowhere Dense Graphs (2015) (59)
Lovász Meets Weisfeiler and Leman (2018) (59)
An existential locality theorem (2001) (59)
Constraint Solving via Fractional Edge Covers (2006) (57)
Tight lower bounds for query processing on streaming and external memory data (2005) (55)
Graph Neural Networks for Prediction of Fuel Ignition Quality (2020) (54)
Approximation Schemes for First-Order Definable Optimisation Problems (2006) (54)
The succinctness of first-order logic on linear orders (2004) (52)
The Quest for a Logic Capturing PTIME (2008) (52)
The Structure of Tractable Constraint Satisfaction Problems (2006) (50)
Dimension Reduction via Colour Refinement (2013) (50)
Logics with Rank Operators (2009) (49)
Generalized Model-Checking Problems for First-Order Logic (2001) (48)
Testing Graph Isomorphism in Parallel by Playing a Game (2006) (47)
Model Theory Makes Formulas Large (2007) (46)
Deciding First-Order Properties of Nowhere Dense Graphs (2017) (45)
Weisfeiler and Leman go Machine Learning: The Story so far (2021) (45)
Bounded nondeterminism and alternation in parameterized complexity theory (2003) (45)
Preservation Under Extensions on Well-Behaved Finite Structures (2005) (44)
Constraint satisfaction with succinctly specified relations (2010) (44)
Finite Variable Logics in Descriptive Complexity Theory (1998) (44)
The Logic of Graph Neural Networks (2021) (42)
The parameterized complexity of database queries (2001) (41)
Machine-based methods in parameterized complexity theory (2005) (41)
Equivalence in Finite-Variable Logics is Complete for Polynomial Time (1996) (39)
Isomorphism Testing for Graphs of Bounded Rank Width (2015) (39)
Power Iterated Color Refinement (2014) (38)
Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs (1999) (38)
Parameterized complexity for the database theorist (2002) (38)
A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory (2013) (37)
Lower bounds for sorting with few random accesses to external memory (2005) (36)
Where First-Order and Monadic Second-Order Logic Coincide (2012) (35)
Bounded fixed-parameter tractability and log2n nondeterministic bits (2004) (33)
Parameterized Approximability of the Disjoint Cycle Problem (2007) (33)
Learnability and Definability in Trees and Similar Structures (2003) (33)
Descriptive and Parameterized Complexity (1999) (32)
Enumerating homomorphisms (2009) (31)
Limitations of Algebraic Approaches to Graph Isomorphism Testing (2015) (30)
Comparing the succinctness of monadic query languages over finite trees (2003) (29)
Reachability and connectivity queries in constraint databases (2000) (28)
Arity Hierarchies (1996) (27)
Model-checking problems as a basis for parameterized intractability (2004) (27)
Canonisation and Definability for Graphs of Bounded Rank Width (2019) (27)
A Faster Isomorphism Test for Graphs of Small Degree (2018) (26)
Learning first-order definable concepts over structures of small degree (2017) (25)
Graph Similarity and Approximate Isomorphism (2018) (24)
An Improved Isomorphism Test for Bounded-tree-width Graphs (2018) (24)
Randomized computations on large data sets: tight lower bounds (2006) (24)
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard (2008) (23)
Graph Neural Networks for Maximum Constraint Satisfaction (2019) (22)
Parameterized Complexity and Subexponential Time (2004) (22)
Probabilistic Databases with an Infinite Open-World Assumption (2018) (21)
Power and limits of the Weisfeiler-Leman algorithm (2020) (20)
Definable Tree Decompositions (2008) (20)
Counting Bounded Tree Depth Homomorphisms (2020) (20)
On first-order topological queries (2000) (20)
Database Query Processing Using Finite Cursor Machines (2007) (20)
Characterisations of Nowhere Dense Graphs (2013) (19)
Parametrized Complexity and Subexponential Time (Column: Computational Complexity) (2004) (19)
Lower bounds for processing data with few random accesses to external memory (2009) (19)
First-Order Query Evaluation with Cardinality Conditions (2017) (19)
Is Polynomial Time Choiceless? (2015) (17)
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus (2019) (16)
Graph Learning with 1D Convolutions on Random Walks (2021) (16)
Computing with Tangles (2015) (15)
Counting Homomorphisms and Partition Functions (2011) (15)
An isomorphism between subexponential and parameterized complexity theory (2006) (15)
Choiceless Polynomial Time on Structures with Small Abelian Colour Classes (2014) (15)
Complete problems for fixed-point logics (1995) (14)
A Finite-Model-Theoretic View on Propositional Proof Complexity (2018) (14)
From polynomial time queries to graph structure theory (2010) (14)
Infinite Probabilistic Databases (2019) (14)
Descriptive complexity of linear equation systems and applications to propositional proof complexity (2017) (14)
Color Refinement and Its Applications (2021) (13)
Recent Advances on the Graph Isomorphism Problem (2020) (12)
RUN-CSP: Unsupervised Learning of Message Passing Networks for Binary Constraint Satisfaction Problems (2019) (12)
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism (2016) (12)
Existential Least Fixed-Point Logic and its Relatives (1997) (12)
Learning MSO-definable hypotheses on strings (2017) (11)
Fixed-parameter tractability and logic (1999) (11)
The Effects of Randomness on the Stability of Node Embeddings (2020) (11)
Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs (2010) (11)
Large Finite Structures with Few Lk-Types (1997) (11)
L-Recursion and a new Logic for Logarithmic Space (2012) (11)
From polynomial time queries to graph structure theory (2011) (10)
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs (2021) (10)
Bounded-Arity Hierarchies in Fixed-Point Logics (1993) (10)
The Complexity of Querying External Memory and Streaming Data (2005) (10)
Quasi-4-Connected Components (2016) (9)
Homomorphism Tensors and Linear Equations (2021) (9)
Isomorphism Testing for Graphs Excluding Small Minors (2020) (9)
The Complexity of Homomorphism Indistinguishability (2019) (9)
Generative Datalog with Continuous Distributions (2020) (8)
Fixed-Point Definability and Polynomial Time (2009) (8)
Characterisations of Nowhere Dense Graphs (Invited Talk) (2013) (8)
The graph isomorphism problem (2020) (8)
A double arity hierarchy theorem for transitive closure logic (1996) (7)
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement (2016) (7)
The Hardness of Embedding Grids and Walls (2017) (7)
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (2014) (7)
Isomorphism, canonization, and definability for graphs of bounded rank width (2021) (7)
Termination orders for three-dimensional rewriting (2006) (6)
On fixed-point logic with counting (2000) (6)
Bounds and Algorithms for Joins via Fractional Edge Covers (2013) (6)
Deep Weisfeiler Leman (2020) (6)
Learnability and Definability in Trees and Similar Structures (2002) (6)
The Complexity of Datalog on Linear Orders (2009) (6)
Some Remarks on Finite Löwenheim-Skolem Theorems (1996) (6)
Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles) (2016) (6)
Classification of properties and their relation to chemical bonding: Essential steps toward the inverse design of functional materials (2022) (5)
Monadic Datalog Containment on Trees (2014) (5)
Order Invariance on Decomposable Structures (2016) (5)
On graph sparsity and structure : colourings and graph decompositions (2016) (5)
Algorithmic Meta Theorems for Sparse Graph Classes (2014) (5)
Tangles and Connectivity in Graphs (2016) (5)
Randomisation and Derandomisation in Descriptive Complexity Theory (2010) (5)
Structural and logical approaches to the graph isomorphism problem (2012) (5)
Automorphism groups of graphs of bounded Hadwiger number (2020) (4)
Large finite structures with few L/sup /spl kappa//-types (1997) (4)
An analysis of the W*-hierarchy (2007) (4)
Bounded fixed-parameter tractability and reducibility (2007) (4)
Independence in Infinite Probabilistic Databases (2020) (3)
Canonization for Lk-equivalence is Hard (1997) (3)
Definable decompositions for graphs of bounded linear cliquewidth (2018) (3)
On the Parameterized Complexity of Learning First-Order Logic (2021) (3)
One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction (2022) (3)
Tuple-Independent Representations of Infinite Probabilistic Databases (2020) (3)
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (2016) (3)
On the Parameterized Complexity of Learning Logic (2021) (2)
Probabilistic Query Evaluation with Bag Semantics (2022) (2)
Database Repairing with Soft Functional Dependencies (2020) (2)
Graph Machine Learning for Design of High-Octane Fuels (2022) (2)
Towards faster isomorphism tests for bounded-degree graphs (2018) (2)
Where First-Order and Monadic Second-Order Logic Coincide (2012) (2)
Probabilistic Data with Continuous Distributions (2021) (1)
Dynamic Database Embeddings with FoRWaRD (2021) (1)
Generative Datalog with Continuous Distributions (2022) (1)
Learning MSO-definable hypotheses on string (2017) (1)
Query evaluation via tree-decompositions: Extended abstract (2001) (1)
09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability (2009) (1)
Weisfeiler-Leman meets Homomorphisms (2018) (1)
Proceedings of the 3rd international conference on Parameterized and exact computation (2008) (1)
Solving AC Power Flow with Graph Neural Networks under Realistic Constraints (2022) (1)
The Expressive Power of Two-Variable Least Fixed-Point Logics (2005) (1)
Logical and Structural Approaches to the Graph Isomorphism Problem (2013) (1)
Physical Pooling Functions in Graph Neural Networks for Molecular Property Prediction (2022) (1)
Symmetry and Similarity (Invited Talk) (2019) (0)
2003 european summer meeting of the association for symbolic logic logic colloquim'03 (2004) (0)
Algorithms for Streaming Graphs (2009) (0)
Graphs with excluded minors (2017) (0)
Simulating Logspace-Recursion with Logarithmic Quantifier Depth (2023) (0)
3-connected components (2017) (0)
Graph Embeddings: Theory meets Practice (2022) (0)
Theory and Practice of SAT Solving (Dagstuhl Seminar 15171) (2015) (0)
The Ackermann Award 2007 (2007) (0)
09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability (2009) (0)
44 11121 – Computational Complexity of Discrete Problems (2011) (0)
05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability (2005) (0)
Graph Similarity Based on Matrix Norms (2022) (0)
Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005 (2006) (0)
Robertson and Seymour's version of the Local Structure Theorem (2017) (0)
Database Theory Column Report on PODS 2014 (2014) (0)
Almost planar completions (2017) (0)
Ordered treelike decompositions (2017) (0)
Session details: Session 7A (2007) (0)
05301 Summary - Exact Algorithms and Fixed-Parameter Tractability (2005) (0)
Book Review (2002) (0)
Bits and pieces (2017) (0)
Almost-embeddable graphs (2017) (0)
Deep End-To-End Learning on Molecular Graphs for Physico-Chemical Property Prediction using Graph Neural Networks : 8th - 9th July 2020 ; 3rd International Conference on Machine Learning an AI in (bio)Chemical Engineering (2020) (0)
Decompositions of almost-embeddable graphs (2017) (0)
Graphs embeddable in a surface (2017) (0)
CS 2 Algorithms and Data Structures Note 3 Sequential Data Structures (0)
Stable Tuple Embeddings for Dynamic Databases (2021) (0)
A COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS WITH (2009) (0)
Some Might Say All You Need Is Sum (2023) (0)
Session details: Session 13B (2007) (0)
Exact algorithms and fixed-parameter tractability (Proceedings Dagstuhl Seminar, July 24-29, 2005) (2006) (0)
Notices (2012) (0)
Datalog on Infinite Structures (2008) (0)
WL meet VC (2023) (0)
The Constraint Satisfaction Problem : Complexity and Approximability 3 CSP duality and trees of bounded pathwidth (2010) (0)
Standard Probabilistic Databases (2020) (0)
Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk) (2014) (0)
REVIEWS-Parameterized complexity theory (2007) (0)
122 15171 – Theory and Practice of SAT Solving Participants (2015) (0)
The Descriptive Complexity of Graph Neural Networks (2023) (0)
Citation for the Test-of-Time Award from LICS 1995 (2015) (0)
Background from graph theory and logic (2017) (0)
Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132) (2022) (0)
Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings (2008) (0)
Graphs of bounded tree width (2017) (0)
Disjoint NP-Pairs and Propositional Proof (2006) (0)
Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121) (2011) (0)
Session details: Data structures and range queries (2014) (0)
Completions of pre-decompositions (2017) (0)
Query Evaluation on CompressedTrees � ( ExtendedAbstract ) (2003) (0)
Model theoretic methods in finite combinatorics : AMS-ASL joint special session, January 5-8, 2009, Washington, DC (2011) (0)
Almost planar graphs (2017) (0)
K5-minor-free graphs (2017) (0)
Explorer Path Queries on Compressed XML (0)
Weisfeiler and Leman's Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk) (2020) (0)
A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk) (2021) (0)
A decomposition-compatible canonization framework for the graph isomorphism problem (2021) (0)

This paper list is powered by the following services:

Other Resources About Martin Grohe

en.wikipedia.org

What Schools Are Affiliated With Martin Grohe?

Martin Grohe is affiliated with the following schools:

Martin Grohe's Academic­Influence.com Rankings

Why Is Martin Grohe Influential?

Martin Grohe's Published Works

Published Works

Other Resources About Martin Grohe

What Schools Are Affiliated With Martin Grohe?

Martin Grohe's AcademicInfluence.com Rankings