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