| 2009 |
|---|
| 112 | EE | Andrei A. Bulatov,
Víctor Dalmau,
Martin Grohe,
Dániel Marx:
Enumerating Homomorphisms.
STACS 2009: 231-242 |
| 111 | EE | Leslie Ann Goldberg,
Martin Grohe,
Mark Jerrum,
Marc Thurley:
A Complexity Dichotomy for Partition Functions with Mixed Signs.
STACS 2009: 493-504 |
| 110 | EE | Martin Grohe,
Götz Schwandtner:
The Complexity of Datalog on Linear Orders
CoRR abs/0902.1179: (2009) |
| 109 | EE | Andrei A. Bulatov,
Víctor Dalmau,
Martin Grohe,
Dániel Marx:
Enumerating Homomorphisms
CoRR abs/0902.1256: (2009) |
| 108 | EE | Martin Grohe,
Dániel Marx:
On tree width, bramble size, and expansion.
J. Comb. Theory, Ser. B 99(1): 218-228 (2009) |
| 2008 |
|---|
| 107 | | Martin Grohe,
Rolf Niedermeier:
Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings
Springer 2008 |
| 106 | EE | Albert Atserias,
Martin Grohe,
Dániel Marx:
Size Bounds and Query Plans for Relational Joins.
FOCS 2008: 739-748 |
| 105 | EE | Manuel Bodirsky,
Martin Grohe:
Non-dichotomies in Constraint Satisfaction Complexity.
ICALP (2) 2008: 184-196 |
| 104 | EE | Kord Eickmeyer,
Martin Grohe,
Magdalena Grüber:
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard.
IEEE Conference on Computational Complexity 2008: 8-18 |
| 103 | EE | Martin Grohe:
The Quest for a Logic Capturing PTIME.
LICS 2008: 267-271 |
| 102 | EE | Martin Grohe:
Definable Tree Decompositions.
LICS 2008: 406-417 |
| 101 | EE | Isolde Adler,
Martin Grohe,
Stephan Kreutzer:
Computing excluded minors.
SODA 2008: 641-650 |
| 100 | EE | Martin Grohe:
Algorithmic Meta Theorems.
WG 2008: 30 |
| 99 | EE | Leslie Ann Goldberg,
Martin Grohe,
Mark Jerrum,
Marc Thurley:
A complexity dichotomy for partition functions with mixed signs
CoRR abs/0804.1932: (2008) |
| 98 | EE | Albert Atserias,
Anuj Dawar,
Martin Grohe:
Preservation under Extensions on Well-Behaved Finite Structures.
SIAM J. Comput. 38(4): 1364-1381 (2008) |
| 2007 |
|---|
| 97 | EE | Martin Grohe,
Martin Hyland,
Johann A. Makowsky,
Damian Niwinski:
The Ackermann Award 2007.
CSL 2007: 589-597 |
| 96 | EE | Martin Grohe,
Magdalena Grüber:
Parameterized Approximability of the Disjoint Cycle Problem.
ICALP 2007: 363-374 |
| 95 | EE | Anuj Dawar,
Martin Grohe,
Stephan Kreutzer,
Nicole Schweikardt:
Model Theory Makes Formulas Large.
ICALP 2007: 913-924 |
| 94 | EE | Martin Grohe,
Yuri Gurevich,
Dirk Leinders,
Nicole Schweikardt,
Jerzy Tyszkiewicz,
Jan Van den Bussche:
Database Query Processing Using Finite Cursor Machines.
ICDT 2007: 284-298 |
| 93 | EE | Anuj Dawar,
Martin Grohe,
Stephan Kreutzer:
Locally Excluding a Minor.
LICS 2007: 270-279 |
| 92 | EE | Rod Downey,
Jörg Flum,
Martin Grohe,
Mark Weyer:
Bounded fixed-parameter tractability and reducibility.
Ann. Pure Appl. Logic 148(1-3): 1-19 (2007) |
| 91 | EE | Martin Grohe,
André Hernich,
Nicole Schweikardt:
Randomized Computations on Large Data Sets: Tight Lower Bounds
CoRR abs/cs/0703081: (2007) |
| 90 | EE | Martin Grohe:
Logic, Graphs, and Algorithms.
Electronic Colloquium on Computational Complexity (ECCC) 14(091): (2007) |
| 89 | EE | Yijia Chen,
Martin Grohe,
Magdalena Grüber:
On Parameterized Approximability.
Electronic Colloquium on Computational Complexity (ECCC) 14(106): (2007) |
| 88 | EE | Isolde Adler,
Georg Gottlob,
Martin Grohe:
Hypertree width and related hypergraph invariants.
Eur. J. Comb. 28(8): 2167-2181 (2007) |
| 87 | EE | Martin Grohe:
The complexity of homomorphism and constraint satisfaction problems seen from the other side.
J. ACM 54(1): (2007) |
| 86 | EE | Yijia Chen,
Martin Grohe:
An Isomorphism Between Subexponential and Parameterized Complexity Theory.
SIAM J. Comput. 37(4): 1228-1258 (2007) |
| 85 | EE | Martin Grohe,
Christoph Koch,
Nicole Schweikardt:
Tight lower bounds for query processing on streaming and external memory data.
Theor. Comput. Sci. 380(1-2): 199-217 (2007) |
| 2006 |
|---|
| 84 | | Rodney G. Downey,
Martin Grohe,
Gerhard J. Woeginger:
Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005
Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2006 |
| 83 | EE | Hubie Chen,
Martin Grohe:
Constraint Satisfaction with Succinctly Specified Relations.
Complexity of Constraints 2006 |
| 82 | EE | Martin Grohe,
Oleg Verbitsky:
Testing Graph Isomorphism in Parallel by Playing a Game.
ICALP (1) 2006: 3-14 |
| 81 | EE | Yijia Chen,
Martin Grohe:
An Isomorphism between Subexponential and Parameterized Complexity Theory.
IEEE Conference on Computational Complexity 2006: 314-330 |
| 80 | EE | Yijia Chen,
Martin Grohe,
Magdalena Grüber:
On Parameterized Approximability.
IWPEC 2006: 109-120 |
| 79 | EE | Anuj Dawar,
Martin Grohe,
Stephan Kreutzer,
Nicole Schweikardt:
Approximation Schemes for First-Order Definable Optimisation Problems.
LICS 2006: 411-420 |
| 78 | EE | Martin Grohe:
The Structure of Tractable Constraint Satisfaction Problems.
MFCS 2006: 58-72 |
| 77 | EE | Martin Grohe,
André Hernich,
Nicole Schweikardt:
Randomized computations on large data sets: tight lower bounds.
PODS 2006: 243-252 |
| 76 | EE | Martin Grohe,
Dániel Marx:
Constraint solving via fractional edge covers.
SODA 2006: 289-298 |
| 75 | EE | Martin Grohe,
Oleg Verbitsky:
Testing Graph Isomorphism in Parallel by Playing a Game
CoRR abs/cs/0603054: (2006) |
| 74 | EE | Yijia Chen,
Martin Grohe:
An Isomorphism between Subexponential and Parameterized Complexity Theory
Electronic Colloquium on Computational Complexity (ECCC)(011): (2006) |
| 73 | EE | Jörg Flum,
Martin Grohe,
Mark Weyer:
Bounded fixed-parameter tractability and log2n nondeterministic bits.
J. Comput. Syst. Sci. 72(1): 34-71 (2006) |
| 2005 |
|---|
| 72 | EE | Rodney G. Downey,
Martin Grohe,
Gerhard J. Woeginger:
05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability.
Exact Algorithms and Fixed-Parameter Tractability 2005 |
| 71 | EE | Rodney G. Downey,
Martin Grohe,
Gerhard J. Woeginger:
05301 Summary - Exact Algorithms and Fixed-Parameter Tractability.
Exact Algorithms and Fixed-Parameter Tractability 2005 |
| 70 | EE | Martin Grohe,
Christoph Koch,
Nicole Schweikardt:
The Complexity of Querying External Memory and Streaming Data.
FCT 2005: 1-16 |
| 69 | EE | Martin Grohe,
Christoph Koch,
Nicole Schweikardt:
Tight Lower Bounds for Query Processing on Streaming and External Memory Data.
ICALP 2005: 1076-1088 |
| 68 | EE | Albert Atserias,
Anuj Dawar,
Martin Grohe:
Preservation Under Extensions on Well-Behaved Finite Structures.
ICALP 2005: 1437-1449 |
| 67 | EE | Martin Grohe,
Stephan Kreutzer,
Nicole Schweikardt:
The Expressive Power of Two-Variable Least Fixed-Point Logics.
MFCS 2005: 422-434 |
| 66 | EE | Martin Grohe,
Nicole Schweikardt:
Lower bounds for sorting with few random accesses to external memory.
PODS 2005: 238-249 |
| 65 | EE | Georg Gottlob,
Martin Grohe,
Nysret Musliu,
Marko Samer,
Francesco Scarcello:
Hypertree Decompositions: Structure, Algorithms, and Applications.
WG 2005: 1-15 |
| 64 | EE | Jörg Flum,
Martin Grohe:
Model-Checking Problems as a Basis for Parameterized Intractability
CoRR abs/cs/0502005: (2005) |
| 63 | EE | Martin Grohe,
Nicole Schweikardt:
The succinctness of first-order logic on linear orders
CoRR abs/cs/0502047: (2005) |
| 62 | EE | Martin Grohe,
Christoph Koch,
Nicole Schweikardt:
Tight Lower Bounds for Query Processing on Streaming and External Memory Data
CoRR abs/cs/0505002: (2005) |
| 61 | EE | Jörg Flum,
Martin Grohe:
Model-checking problems as a basis for parameterized intractability.
Logical Methods in Computer Science 1(1): (2005) |
| 60 | EE | Martin Grohe,
Nicole Schweikardt:
The succinctness of first-order logic on linear orders.
Logical Methods in Computer Science 1(1): (2005) |
| 59 | EE | Yijia Chen,
Jörg Flum,
Martin Grohe:
Machine-based methods in parameterized complexity theory.
Theor. Comput. Sci. 339(2-3): 167-199 (2005) |
| 58 | EE | Andrei A. Bulatov,
Martin Grohe:
The complexity of partition functions.
Theor. Comput. Sci. 348(2-3): 148-186 (2005) |
| 2004 |
|---|
| 57 | EE | Andrei A. Bulatov,
Martin Grohe:
The Complexity of Partition Functions.
ICALP 2004: 294-306 |
| 56 | EE | Jörg Flum,
Martin Grohe,
Mark Weyer:
Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits.
ICALP 2004: 555-567 |
| 55 | EE | Jörg Flum,
Martin Grohe:
Model-Checking Problems as a Basis for Parameterized Intractability.
LICS 2004: 388-397 |
| 54 | EE | Martin Grohe,
Nicole Schweikardt:
The Succinctness of First-Order Logic on Linear Orders.
LICS 2004: 438-447 |
| 53 | EE | Martin Grohe,
Stefan Wöhrle:
An existential locality theorem.
Ann. Pure Appl. Logic 129(1-3): 131-148 (2004) |
| 52 | EE | Markus Frick,
Martin Grohe:
The complexity of first-order and monadic second-order logic revisited.
Ann. Pure Appl. Logic 130(1-3): 3-31 (2004) |
| 51 | | Jörg Flum,
Martin Grohe:
Parametrized Complexity and Subexponential Time (Column: Computational Complexity).
Bulletin of the EATCS 84: 71-100 (2004) |
| 50 | EE | Martin Grohe:
Computing crossing numbers in quadratic time.
J. Comput. Syst. Sci. 68(2): 285-302 (2004) |
| 49 | EE | Jörg Flum,
Martin Grohe:
The Parameterized Complexity of Counting Problems.
SIAM J. Comput. 33(4): 892-922 (2004) |
| 48 | EE | Martin Grohe,
György Turán:
Learnability and Definability in Trees and Similar Structures.
Theory Comput. Syst. 37(1): 193-220 (2004) |
| 2003 |
|---|
| 47 | EE | Martin Grohe,
Nicole Schweikardt:
Comparing the Succinctness of Monadic Query Languages over Finite Trees.
CSL 2003: 226-240 |
| 46 | EE | Martin Grohe:
The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side.
FOCS 2003: 552-561 |
| 45 | EE | Yijia Chen,
Jörg Flum,
Martin Grohe:
Bounded Nondeterminism and Alternation in Parameterized Complexity Theory.
IEEE Conference on Computational Complexity 2003: 13-29 |
| 44 | EE | Markus Frick,
Martin Grohe,
Christoph Koch:
Query Evaluation on Compressed Trees (Extended Abstract).
LICS 2003: 188- |
| 43 | EE | Peter Buneman,
Martin Grohe,
Christoph Koch:
Path Queries on Compressed XML.
VLDB 2003: 141-152 |
| 42 | EE | Martin Grohe:
Local Tree-Width, Excluded Minors, and Approximation Algorithms.
Combinatorica 23(4): 613-632 (2003) |
| 41 | EE | Jörg Flum,
Martin Grohe:
Describing parameterized complexity classes.
Inf. Comput. 187(2): 291-319 (2003) |
| 40 | EE | Michael Benedikt,
Martin Grohe,
Leonid Libkin,
Luc Segoufin:
Reachability and connectivity queries in constraint databases.
J. Comput. Syst. Sci. 66(1): 169-206 (2003) |
| 2002 |
|---|
| 39 | EE | Jörg Flum,
Martin Grohe:
The Parameterized Complexity of Counting Problems.
FOCS 2002: 538- |
| 38 | EE | Markus Frick,
Martin Grohe:
The Complexity of First-Order and Monadic Second-Order Logic Revisited.
LICS 2002: 215-224 |
| 37 | EE | Jörg Flum,
Martin Grohe:
Describing Parameterized Complexity Classes.
STACS 2002: 359-371 |
| 36 | EE | Martin Grohe,
György Turán:
Learnability and Definability in Trees and Similar Structures.
STACS 2002: 645-658 |
| 35 | EE | Martin Grohe,
Luc Segoufin:
On first-order topological queries.
ACM Trans. Comput. Log. 3(3): 336-358 (2002) |
| 34 | EE | Martin Grohe:
Large Finite Structures with Few Lk-Types.
Inf. Comput. 179(2): 250-278 (2002) |
| 33 | EE | Jörg Flum,
Markus Frick,
Martin Grohe:
Query evaluation via tree-decompositions.
J. ACM 49(6): 716-752 (2002) |
| 32 | EE | Martin Grohe:
Parameterized Complexity for the Database Theorist.
SIGMOD Record 31(4): 86-96 (2002) |
| 2001 |
|---|
| 31 | EE | Martin Grohe,
Stefan Wöhrle:
An Existential Locality Theorem.
CSL 2001: 99-114 |
| 30 | EE | Jörg Flum,
Markus Frick,
Martin Grohe:
Query Evaluation via Tree-Decompositions.
ICDT 2001: 22-38 |
| 29 | EE | Martin Grohe:
The Parameterized Complexity of Database Queries.
PODS 2001: 82-92 |
| 28 | EE | Martin Grohe:
Generalized Model-Checking Problems for First-Order Logic.
STACS 2001: 12-26 |
| 27 | EE | Martin Grohe:
Computing crossing numbers in quadratic time.
STOC 2001: 231-236 |
| 26 | EE | Martin Grohe,
Thomas Schwentick,
Luc Segoufin:
When is the evaluation of conjunctive queries tractable?
STOC 2001: 657-666 |
| 25 | EE | Markus Frick,
Martin Grohe:
Deciding first-order properties of locally tree-decomposable structures.
J. ACM 48(6): 1184-1206 (2001) |
| 24 | EE | Jörg Flum,
Martin Grohe:
Fixed-Parameter Tractability, Definability, and Model-Checking.
SIAM J. Comput. 31(1): 113-145 (2001) |
| 2000 |
|---|
| 23 | EE | Martin Grohe,
Luc Segoufin:
On First-Order Topological Queries.
LICS 2000: 349-360 |
| 22 | EE | Michael Benedikt,
Martin Grohe,
Leonid Libkin,
Luc Segoufin:
Reachability and Connectivity Queries in Constraint Databases.
PODS 2000: 104-115 |
| 21 | EE | Martin Grohe:
Isomorphism testing for embeddable graphs through definability.
STOC 2000: 63-72 |
| 20 | EE | Martin Grohe,
Thomas Schwentick:
Locality of order-invariant first-order formulas.
ACM Trans. Comput. Log. 1(1): 112-130 (2000) |
| 19 | EE | Markus Frick,
Martin Grohe:
Deciding first-order properties of locally tree-decomposable structures
CoRR cs.DS/0004007: (2000) |
| 18 | EE | Martin Grohe:
Computing Crossing Numbers in Quadratic Time
CoRR cs.DS/0009010: (2000) |
| 17 | | Jörg Flum,
Martin Grohe:
On Fixed-Point Logic With Counting.
J. Symb. Log. 65(2): 777-787 (2000) |
| 1999 |
|---|
| 16 | | Martin Grohe:
Descriptive and Parameterized Complexity.
CSL 1999: 14-31 |
| 15 | EE | Markus Frick,
Martin Grohe:
Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs.
ICALP 1999: 331-340 |
| 14 | EE | Martin Grohe,
Julian Mariño:
Definability and Descriptive Complexity on Databases of Bounded Tree-Width.
ICDT 1999: 70-82 |
| 13 | EE | Jörg Flum,
Martin Grohe:
Fixed-parameter tractability, definability, and model checking
CoRR cs.CC/9910001: (1999) |
| 12 | EE | Martin Grohe:
Equivalence in Finite-Variable Logics is Complete for Polynomial Time.
Combinatorica 19(4): 507-532 (1999) |
| 1998 |
|---|
| 11 | | Martin Grohe:
Fixed-Point Logics on Planar Graphs.
LICS 1998: 6-15 |
| 10 | EE | Martin Grohe,
Thomas Schwentick:
Locality of Order-Invariant First-Order Formulas.
MFCS 1998: 437-445 |
| 9 | EE | Martin Grohe:
Finite variable logics in descriptive complexity theory.
Bulletin of Symbolic Logic 4(4): 345-398 (1998) |
| 1997 |
|---|
| 8 | | Martin Grohe:
Canonization for Lk-equivalence is Hard.
CSL 1997: 220-238 |
| 7 | EE | Martin Grohe:
Large Finite Structures with Few Lk-Types.
LICS 1997: 216-227 |
| 6 | | Martin Grohe:
Existential Least Fixed-Point Logic and its Relatives.
J. Log. Comput. 7(2): 205-228 (1997) |
| 1996 |
|---|
| 5 | | Martin Grohe:
Equivalence in Finite-Variable Logics is Complete for Polynomial Time.
FOCS 1996: 264-273 |
| 4 | | Martin Grohe:
Arity Hierarchies.
Ann. Pure Appl. Logic 82(2): 103-163 (1996) |
| 3 | | Martin Grohe:
Some Remarks on Finite Löwenheim-Skolem Theorems.
Math. Log. Q. 42: 569-571 (1996) |
| 1995 |
|---|
| 2 | | Martin Grohe:
Complete Problems for Fixed-Point Logics.
J. Symb. Log. 60(2): 517-527 (1995) |
| 1993 |
|---|
| 1 | | Martin Grohe:
Bounded-Arity Hierarchies in Fixed-Point Logics.
CSL 1993: 150-164 |
