Person

Dr. rer. nat., Universitätsprofessor

Martin Grohe

Nicht verfügbar
Fachgruppe Informatik

Adresse

Gebäude: E1, 1. Etage

Raum: 4116a

Ahornstraße 55

52074 Aachen

Kontakt

workPhone
Telefon: +49 241 80 21700
Fax: +49 241 80 22215

Sprechstunde

Montag, 15:00 - 16:00 Uhr
 

Forschungsinteressen

Logik, Algorithmen und Komplexität, Datenbanktheorie, Graphentheorie, Lerntheorie

 

Bücher

Titelseiten der Bücher

Titel Autoren Erschienen

Descriptive Complexity, Canonisation, and Definable Graph Structure Theory

Preliminary draft

Lecture Notes in Logic

Martin Grohe

Preliminary Draft, 2013

Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017

Model Theoretic Methods in Finite Combinatorics Marting Grohe edited jointly with Janos Makowsky Contemporary Mathematics 558, American Mathematical Society, 2011
Parameterized Complexity Theory Martin Grohe, Jörg Flum Springer-Verlag, 2006
 
 

Publikationen

Titel Autor(en) Erschienen in

Lovász meets Weisfeiler and Leman

Holger Dell, Martin Grohe, Gaurav Rattan Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

An improved isomorphism test for bounded-tree-width graphs

Martin, Grohe, Daniel Neuen, Pascal Schweitzer, Daniel Wiebking

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Definable Decompositions for Graphs of Bounded Linear Clique Width

Martin Grohe, Mikolaj Bojanczyk, Michal Pilipczuk Proceedings of the 33rd ACM-IEEE Symposium on Logic in Computer Science, 2018
First-Order Query Evaluation with Cardinality Conditions Martin Grohe, Nicole Schweikardt Proceedings of the 37th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2018
Color Refinement and its Applications Martin Grohe, Kristian Kersting, Martin Mladenov, Pascal Schweitzer

Preliminary Draft of a Chapter, 2017

Guy Van den Broeck, Kristian Kersting, Sriraam Natarajan, David Poole, An Introduction to Lifted Probabilistic Inference, Cambridge University Press

Learning MSO-Definable Hypotheses on Strings Martin Grohe, Christof Löding, Martin Ritzert Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017

The Hardness of Embedding Grids and Walls

Martin Grohe, Yijia Chen, BingKai Lin

Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, 2017

Learning first-order definable concepts over structures of small degree

Conference version

Martin Grohe, Martin Ritzert

Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017
Descriptive Complexity of Solving Linear Equation Systems and its Applications

Martin Grohe, Wied Pakusa

Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017
Deciding First-Order properties of Nowhere Dense Graphs Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

Journal of the ACM 64(3)

Proceedings of the 46th ACM Symposium on Theory of Computing (STOC'14), pp.89-98, 2014

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement

Lecture Notes in Computer Science

Martin Grohe, Paul Bonsma, Christoph Berkholz

Theory of Computing Systems 60(4):581-614, 2017

Proceedings of the 21st Annual European Symposium on Algorithms (ESA 2013)

Lecture Notes in Computer Science 8125, pp.145-156, 2013

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism Martin Grohe, Christoph Berkholz Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.327-339, 2017
Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles) Martin Grohe CoRR abs/1605.06704, 2016
Quasi-4-Connected Components Martin Grohe

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, 2016

Order Invariance on Decomposable Structures

Conference version

Martin Grohe, Michael Elberfeld, Marlin Frickenschmidt Proceedings of the 31st IEEE Symposium on Logic in Computer Science (LICS 2016), pp.397-406, 2016

Computing with Tangles

Martin Grohe, Pascal Schweitzer

SIAM Journal on Discrete Mathematics, 30(2):1213-1247, 2016

Proceedings of the 47th ACM Symposium on Theory of Computing (STOC'15), pp.683-692, 2015

Where First-Order and Monadic Second-Order Logic Coincide Martin Grohe, Michael Elberfeld, Till Tantau

ACM Transactions on Computational Logic, 17(4):25:1-25:18, 2016

Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LICS 2016, pp.265-274, 2012

Tangles and Connectivity in Graphs

Lecture Notes in Computer Science

Martin Grohe

roceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA 2016)

Lecture Notes in Computer Science 9618, pp.24-42, 2016

Colouring and Covering Nowhere Dense Graphs

Lecture Notes in Computer Science

Martin grohe, S. Kreutzer and R. Rabinovich and S. Siebertz, K. Stavropoulos

Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'15)

Lecture Notes in Computer Science 9224, pp.325-338, 2016

Isomorphism Testing for Graphs of Bounded Rank Width Martin Grohe, Pascal Schweitzer Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS15), pp.1010-1029, 2015

Is Polynomial Time Choiceless

Lecture Notes in Computer Science

Martin Grohe, Erich Grädel

Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday

Lecture Notes in Computer Science 9300, pp.193-209, 2015

Limitations of Algebraic Approaches to Graph Isomorphism Testing

Lecture Notes in Computer Science

Martin Grohe, Christoph Berkholz

Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015), Part II

Lecture Notes in Computer Science 9134, pp.155-166, 2015

Logical Characterisations of Complexity Classes

Encyclopedia of Applied and Computational Mathematics

Martin Grohe Encyclopedia of Applied and Computational Mathematics, Springer Verlag, 2015
Pebble Games and Linear Equations Martin Grohe, Martin Otto

Journal of Symbolic Logic 80(3), 2015

Proceedings of the 26th International Workshop on Computer Science Logic (CSL'12), Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, 2012

Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs

Conference version

Martin Grohe, Dániel Marx

SIAM Journal on Computing 44(1):114-159, 2015

Proceedings of the 44th ACM Symposium on Theory of Computing (STOC'12), pp.173-192, 2012

Constraint Solving via Fractional Edge Covers Martin grohe, Dániel Marx

ACM Transactions on Algorithms 11(1), 2014

Proceedings of the of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp.289-298, 2006

Choiceless Polynomial Time on Structures with Small Abelian Colour Classes

Lecture Notes in Computer Science

Martin Grohe, Faried Abu Zaid, Erich Grädel, Wied Pakusa

Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), Part I

Lecture Notes in Computer Science 8634, pp.50-62, 2014

Dimension Reduction via Colour Refinement

Lecture Notes in Computer Science

Martin Grohe, Kristian Kersting and Martin Mladenov, Erkal Selman

Proceedings of the 22nd Annual European Symposium on Algorithms

Lecture Notes in Computer Science 8737, pp. 505–516, 2014

Power Iterated Color Refinement Martin grohe, Kristian Kersting, Martin Mladenov, Roman Garnett Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI'14), pp. 1904–1910, 2014

Algorithmic Meta Theorems for Sparse Graph Classes

Lecture Notes in Computer Science

Martin Grohe

Proceedings of the 9th International Computer Science Symposium in Russia (CSR'14)

Lecture Notes in Computer Science 8476, pp.16-22, 2014

Monadic Datalog Containment on Trees

Martin Grohe, André Frochaux, Nicole Schweikardt

SIAM Journal on Computing 42(4):1737-1767, 2013

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739-748, 2008

Size bounds and query plans for relational joins Martin Grohe, Albert Atserias and Dániel Marx

SIAM Journal on Computing 42(4):1737-1767, 2013

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739-748, 2008

Characterisations of Nowhere Dense Graphs

LIPICS - Leibniz International Proceedings in Informatics

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

Proceedings of the 32nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

LIPICS - Leibniz International Proceedings in Informatics 24, pp.21-40, 2013

Bounds and Algorithms for Joins via Fractional Edge Covers

Lecture Notes in Computer Science

Martin Grohe

In Search of Elegance in the Theory and Practice of Computation, Essays Dedicated to Peter Buneman

Lecture Notes in Computer Science 8000, pp.321-338, 2013

A Simple Algorithm for the Graph Minor Decomposition — Logic Meets Structural Graph Theory — Martin Grohe, Ken-ichi Kawarabayashi, Bruce Reed Proceedings of the of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp.414-431, 2013
Fixed-Point Definability and Polynomial Time on Graph with Excluded Minors Martin Grohe

Journal of the ACM 59(5), 2012

Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LICS'10), 2010

Enumerating Homomorphisms Martin Grohe, Andrei A. Bulatov, Victor Dalmau, Dániel Marx

Journal of Computer and System Sciences 78:638-650, 2012

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.231-242, 2009

L-Recursion and a new Logic for Logarithmic Space Martin Grohe, Berit Grußien, André Hernich, Bastian Laubner

Logical Methods in Computer Science 9(1), 2012

Proceedings of the 25th International Workshop on Computer Science Logic (CSL'11)

Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, 2011

Methods for Algorithmic Meta Theorems Martin Grohe, Stephan Kreutzer Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011
Counting Homomorphisms and Partition Functions Martin Grohe, Marc Thurley Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011
From Polynomial Time Queries to Graph Structure Theory Martin Grohe Communications of the ACM 54(6):104-112, 2011
Finding Topological Subgraphs is Fixed-Parameter Tractable Martin Grohe, Dániel Marx, Ken-Ich Kawarbayashi, Paul Wollan roceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pp.479-488, 2011
Randomisation and Derandomisation in Descriptive Complexity Theory

Martin Grohe, Kord Eickmeyer

Logical Methods in Computer Science, Volume 7, Issue 3, 2011

Proceedings of the 24th International Workshop on Computer Science Logic (CSL'10), pp.275-289, 2010

Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs

Lecture Notes in Computer Science

Martin Grohe

Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday

Lecture Notes in Computer Science 6300, pp.328-353, 2010

A complexity dichotomy for partition functions with mixed signs Martin Grohe, Leslie Ann Goldberg, Mark Jerrum, Marc Thurley

SIAM Journal on Computing 39:336-402, 2010

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.493-504, 2009

Constraint satisfaction problems with succinctly specified relations Martin Grohe, Hubie Chen Journal of Computer and System Sciences 76(8):847-860, 2010

Fixed-Point Definability and Polynomial Time

Slides of my CSL-talk

Martin Grohe Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), pp.20-23, 2009
Logics with Rank Operators Martin Grohe, Anuj Dawar, Bjarki Holm, Bastian Laubner Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS'09), pp.113-122, 2009
Lower bounds for processing data with few random accesses to external memory Martin Grohe, Andre Hernich, Nicole Schweikardt

Journal of the ACM, 56(3), 2009

Full version of PODS'05 and PODS'06 papers

Database query processing using finite cursor machines

Lecture Notes in Computer Science

Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, Jan Van den Bussche

Theory of Computing Systems, 44:533-560, 2009

Proceedings of the 11th International Conference on Database Theory (ICDT'07)

Lecture Notes in Computer Science 4353, pp.284-298, 2007

The Complexity of Datalog on Linear Orders Martin Grohe, Götz Schwandtner Logical Methods in Computer Science, 5(1), 2009
On tree width, bramble size, and expansion Martin Grohe, Dániel Marx Journal of Combinatorial Theory, Series B 99:218-228, 2009

Preservation under Extensions on Well-Behaved Finite Structures

Lecture Notes in Computer Science

Abstract

Martin Grohe, Albert Atserias, Anuj Dawar

SIAM Journal on Computing, 38:1364-1381, 2008

Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05)

Lecture Notes in Computer Science 3580, pp.1437-1450, 2005

Non-dichotomies in constraint satisfaction complexity

Lecture Notes in Computer Science

Martin Grohe, Manuel Bodirsky

roceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08, Track B)

Lecture Notes in Computer Science 5126, pp.184-196, 2008

Definable tree decompositions Martin Grohe Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.406-417, 2008
The quest for a logic capturing PTIME Martin Grohe Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.267-271, 2008
Approximation of natural W[P]-complete minimisation problems is hard Martin Grohe, Kord Eickmeyer, Magdalena Grüber Proceedings of the 23rd IEEE Conference on Computational Complexity (CCC'08), pp.8-18, 2008
Computing excluded minors Martin grohe, Isolde Adler, Stephan Kreutzer Proceedings of the of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp.641-650, 2008
Logic, graphs, and algorithms Martin Grohe, Logic and Automata – History and Perspectives, Amsterdam University Press, 2007
An Isomorphism between Subexponential and Parameterized Complexity Theory Martin Grohe, Yijia Chen

SIAM Journal on Computing 37:1228-1258, 2007

Proceedings of the 21st IEEE Conference on Computational Complexity (CCC'06), pp.314-328, 2006

Bounded Fixed-Parameter Tractability and Reducibility Martin Grohe, Rod Downey, Jörg Flum, Mark Weyer Annals of Pure and Applied Logic 148:1-19, 2007

Parameterized Approximability of the Disjoint Cycle Problem

Lecture Notes in Computer Science

Martin Grohe, Magdalena Grüber

Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A)

Lecture Notes in Computer Science 4596, pp.363-374, 2007

Model Theory Makes Formulas Large

Lecture Notes in Computer Science

Martin Grohe, Anuj Dawar, Stephan Kreutzer, Nicole Schweikardt

Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track B)

Lecture Notes in Computer Science 4596, pp.913-924, 2007

Locally Excluding a Minor Martin Grohe, Anuj Dawar, Stephan Kreutzer Proceedings of the 21st IEEE Symposium on Logic in Computer Science (LICS'07), pp.270-279, 2007

The complexity of homomorphism and constraint satisfaction problems seen from the other side

Abstract

Martin Grohe

Journal of the ACM, 54(1), 2007

Proceedings of the 44th IEEE Symposium on Foundations of Comupter Science (FOCS'03), pp.552-561, 2003

Hypertree-Width and Related Hypergraph Invariants

DMTCS Proceedings Series

Martin Grohe, Isolde Adler and Georg Gottlob

European Journal of Combinatorics, 28:2167-2181, 2007

Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05)

DMTCS Proceedings Series, Volume AE, pp.5-10, 2005

Tight Lower Bounds for Query Processing on Streaming and External Memory Data External Memory

Lecture Notes in Computer Science

Abstract

Martin Grohe, Christoph Koch, Nicole Schweikardt

Theoretical Computer Science 380:199-217, 2007

Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05)

Lecture Notes in Computer Science 3580, pp.1076-1088, 2005

An analysis of the W*-hierarchy Martin Grohe, Yijia Chen, Jörg Flum Journal of Symbolic Logic 72:513-534, 2007

On parameterized approximability

Lecture Notes in Computer Science

Martin Grohe, Yijia Chen, Magdalena Grüber

Proceedings of the 2nd International Workshop on Parameterized and Exact Computation

Lecture Notes in Computer Science 4169, pp.109-120, 2006

Approximation Schemes for First-Order Definable Optimisation Problems Martin Grohe, Anuj Dawar, Stephan Kreutzer, Nicole Schweikardt Proceedings of the 21st IEEE Symposium on Logic in Computer Science, pp.411-420, 2006

The structure of tractable constraint satisfaction problems

Lecture Notes in Computer Science

Martin Grohe

roceedings of the 31st Symposium on Mathematical Foundations of Computer Science

Lecture Notes in Computer Science 4162, pp.58-72, 2006

Testing Graph Isomorphism in Parallel by Playing a Game

Lecture Notes in Computer Science

Martin Grohe, Oleg Verbitzky

Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Part I

Lecture Notes in Computer Science 4051, pp.3-14, 2006

Randomized Computations on Large Data Sets: Tight Lower Bounds Martin Grohe, Andre Hernich, Nicole Schweikardt Proceedings of the 25th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'06), pp.243-252, 2006

Bounded fixed-parameter tractability and log2n nondeterministic bits

Lecture Notes in Computer Science

Abstract

Martin Grohe, örg Flum, Mark Weyer

Journal of Computer and System Sciences 72:34-71, 2006

Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04)

Lecture Notes in Computer Science 3142, pp.555-567, 2004

The complexity of partition functions

Lecture Notes in Computer Science

Abstract

Martin Grohe, Andrei Bulatov

Theoretical Computer Science 348:148-186, 2005

Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04)

Lecture Notes in Computer Science 3142, pp. 294-306, 2004

Hypertree Decompositions: Structure, Algorithms, and Applications

Lecture Notes in Computer Science

Abstract

Martin Grohe, Georg Gottlob, Nysret Musliu, Marko Samer, Francesco Scarcello

Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05)

Lecture Notes in Computer Science , pp.1-15, 2005

The expressive power of two-variable least fixed-point logics

Lecture Notes in Computer Science

Abstract

Martin Grohe, Stephan Kreutzer, Nicole Schweikardt

Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS'05)

Lecture Notes in Computer Science , pp.422-434, 2005

The succinctness of first-order logic on linear orders Martin Grohe, Nicole Schweikardt

Logical Methods in Computer Science, 1(1), 2005

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp. 438-447, 2004

Machine-based methods in parameterized complexity theory

Abstract

Martin Grohe, Yijia Chen, Jörg Flum

Theoretical Computer Science., 339:167-199, 2005

The complexity of querying external memory and streaming data

Lecture Notes in Computer Science

Abstract

Martin Grohe, Christoph Koch, Nicole Schweikardt

Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT'05)

Lecture Notes in Computer Science 3623, pp.1-16, 2005

Lower Bounds for Sorting with Few Random Accesses to External Memory

Abstract

Martin Grohe, Nicole Schweikardt Proceedings of the 24th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'05), pp.238-249, 2005
Model-Checking Problems as a Basis for Parameterized Intractability Martin Grohe, Jörg Flum

Logical Methods in Computer Science 1(1), 2005

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp.388-397, 2004

The complexity of first-order and monadic second-order logic revisited

Abstract

Martin Grohe, Markus Frick

Annals of Pure and Applied Logic 130: 3-31, 2004

Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02), pp. 215-224, 2002

Parameterized Complexity and Subexponential Time Martin Grohe, Jörg Flum Bulletin of the European Association for Theoretical Computer Science 84, October 2004

The parameterized complexity of counting problems

Abstract

Martin Grohe, Jörg Flum

SIAM Journal on Computing 33:892-922, 2004

Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02), pp. 538-547, 2002

An Existential Locality Theorem

Lecture Notes in Computer Science

Abstract

Martin Grohe, Stefan Wöhrle

Annals of Pure and Applied Logic, 129: 131-148, 2004

Proceedings of the 10th Annual Conference of the European Association for Computer Science Logic (CSL'01)

Lecture Notes in Computer Science 2142, pp.99-114, Springer-Verlag 2001

Computing Crossing Numbers in Quadratic Time

Abstract

Martin Grohe

Journal of Computer and System Sciences, 68(2):285-302, 2004

Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.231-236, 2001

Learnability and Definability in Trees and Similar Structures

Abstract

Martin Grohe, Gyorgy Turan

Theory of Computing Systems 37(1):193-220, 2004

Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS'02)

Lecture Notes in Computer Science 2285, pp.645-658, Springer-Verlag 2002

Local tree-width, excluded minors, and approximation algorithms

Abstract

Martin Grohe Combinatorica 23(4):613-632, 2003

Describing Parameterized Complexity Classes

Lecture Notes in Computer Science

Abstract

Martin Grohe, Jörg Flum

Information and Computation 187: 291-319, 2003

Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS'02)

Lecture Notes in Computer Science 2285, pp.359-371, Springer-Verlag 2002

Comparing the succinctness of monadic query languages over finite trees

Lecture Notes in Computer Science

Abstract

Martin Grohe, Nicole Schweikardt

RAIRO - Theoretical Informatics and Applications (ITA) 38:343-373, 2004

Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03)

Lecture Notes in Computer Science 2803, pp.226-240, 2003

Path Queries on Compressed XML Martin Grohe, Peter Buneman, Christoph Koch Proceedings of the 29th Conference on Very Large Data Bases (VLDB 2003), pp.141-152, 2003
Query Evaluation on Compressed Trees Martin Grohe, Markus Frick, Christoph Koch Conference version in Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS'03), pp.188-197, 2003

Bounded Nondeterminism and Alternation in Parameterized Complexity Theory

Abstract

Martin Grohe, Yijia Chen, Jörg Flum Proceedings of the 18th IEEE Conference on Computational Complexity (CCC'03), pp.13-29, 2003

Reachability and Connectivity Queries in Constraint Databases

Abstract

Martin Grohe, Michael Benedikt, Leonid Libkin, Luc Segoufin

Journal of Computer System Sciences 66(1):169-206, 2003

roceedings of the 19th ACM Symposium on Principles of Database Systems (PODS'00), 2000

Parameterized Complexity for the Database Theorist Martin Grohe SIGMOD Record 31(4), 2002

Query evaluation via tree-decompositions

Lecture Notes in Computer Science

Abstract

Martin Grohe, Jörg Flum, Markus Frick

Journal of the ACM 49:716-752, 2002

Proceedings of the 8th International Conference on Database Theory

Lecture Notes in Computer Science 1973, Springer-Verlag, 2001

On first-order topological queries

Abstract

Martin Grohe, Luc Segoufin

ACM Transactions on Computational Logic 3(3):336-358, 2002

Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000

Large finite structures with few Lk-types

Abstract

Martin Grohe

Information and Computation 179(2): 250-278, 2002

Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, 1997

When is the evaluation of conjunctive queries tractable?

Abstract

Martin Grohe, Thomas Schwentick, Luc Segoufin Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.657-666, 2001

The Parameterized Complexity of Database Queries

Abstract

Martin Grohe Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'01), pp.82-92, 2001

Fixed-parameter tractability, definability, and model checking

Abstract

Martin Grohe, Jörg Flum SIAM Journal on Computing 31:113-145, 2001

Generalized model-checking problems for first-order logic

Abstract

Martin Grohe

Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01)

Lecture Notes in Computer Science 2010, pp.12-26, Springer-Verlag 2001

Deciding first-order properties of locally tree-decomposable structures

Lecture Notes in Computer Science

Martin Grohe, Markus Frick

Journal of the ACM 48:1184-1206, 2001

Proceedings of the 26th International Colloquium on Automata, Languages, and Programming

Lecture Notes in Computer Science 1644, Springer-Verlag, 1999

Isomorphism testing for embeddable graphs through definability

Abstract

Martin Grohe Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000

Locality of order-invariant first-order formulas

Lecture Notes in Computer Science

Abstract

Martin Grohe, Thomas Schwentick

ACM Transactions on Computational Logic 1:112-130, 2000

Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science

Lecture Notes in Computer Science 1450, Springer-Verlag, 1998

On fixed-point logic with counting Martin Grohe, Jörg Flum

Journal of Symbolic Logic 65:777- 787, 2000

Equivalence in finite-variable logics is complete for polynomial time Martin Grohe Combinatorica 19:507-532, 1999

Descriptive and parameterized complexity

Abstract

Martin Grohe

Computer Science Logic, 13th Workshop (CSL'99)

Lecture Notes in Computer Science 1683, Springer-Verlag, 1999

Definability and descriptive complexity on databases of bounded tree-width

Lecture Notes in Computer Science

Abstract

Martin Grohe, Julian Marino

Proceedings of the 7th International Conference on Database Theory (ICDT'99)

Lecture Notes in Computer Science 1540, Springer-Verlag, 1999

Zur Struktur dessen, was wirklich berechenbar ist Martin Grohe, Heinz-Dieter Ebbinghaus Philosophia Naturalis 36:91-116, 1999
Finite variable logics in descriptive complexity theory Martin Grohe

Bulletin of Symbolic Logic 4:345-398, 1998

Fixed-point logics on planar graphs

Abstract

Martin Grohe Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS'98), 1998

Canonization for L k -equivalence is hard

Lecture Notes in Computer Science

Abstract

Martin Grohe

Computer Science Logic (CSL'97), 11th Workshop, 1997

Lecture Notes in Computer Science 1414, Springer Verlag 1998

Existential least fixed-point logic and its relatives

Abstract

Martin Grohe Journal of Logic and Computation 7: 205-228, 1997

Arity hierarchies

Abstract

Martin Grohe Annals of Pure and Applied Logic 82: 103-163, 1996

Some remarks on finite Löwenheim-Skolem theorems

Abstract

Martin Grohe Mathematical Logic Quarterly 42: 569-571, 1996

A double arity hierarchy theorem for transitive closure logic

Abstract

Martin Grohe, Lauri Hella Archive for Mathematical Logic 35:157-171, 1996

Complete Problems for fixed-point logics

Abstract

Martin Grohe Journal of Symbolic Logic 60: 517-527, 1995

Bounded-arity hierarchies in fixed-point logics

Lecture Notes in Computer Science

Abstract

Martin Grohe

Computer Science Logic (CSL'93), 7th Workshop, Swansea 1993

Lecture Notes in Computer Science 832, Springer Verlag

The Complexity of Finite-Variable Theories Martin Grohe Habilitationsschrift at the Albert-Ludwigs-Universität Freiburg, November 1997
The Structure of Fixed-Point Logics Martin Grohe Dissertation at the Albert-Ludwigs-Universität Freiburg, December 1994
Fixpunktlogiken in der endlichen Modelltheorie Martin Grohe Diplomarbeit at the Albert-Ludwigs-Universität Freiburg, April 1992