Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Martin Grohe
2010 – today
- 2013
[j49]Albert Atserias, Martin Grohe, Dániel Marx: Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42(4): 1737-1767 (2013)- [c77]Christoph Berkholz, Paul Bonsma, Martin Grohe: Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. ESA 2013: 145-156
- [c76]
- [c75]Martin Grohe, Ken-ichi Kawarabayashi, Bruce A. Reed: A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory. SODA 2013: 414-431
- [i22]Martin Grohe, Kristian Kersting, Martin Mladenov, Erkal Selman: Dimension Reduction via Colour Refinement. CoRR abs/1307.5697 (2013)
- 2012
- [j48]Martin Grohe, Berit Grußien, André Hernich, Bastian Laubner: L-Recursion and a new Logic for Logarithmic Space. Logical Methods in Computer Science 9(1) (2012)
- [j47]Martin Grohe: Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM 59(5): 27 (2012)
- [j46]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating homomorphisms. J. Comput. Syst. Sci. 78(2): 638-650 (2012)
- [c74]
- [c73]Michael Elberfeld, Martin Grohe, Till Tantau: Where First-Order and Monadic Second-Order Logic Coincide. LICS 2012: 265-274
- [c72]
- [c71]Martin Grohe, Dániel Marx: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. STOC 2012: 173-192
- [i21]
- [i20]Michael Elberfeld, Martin Grohe, Till Tantau: Where First-Order and Monadic Second-Order Logic Coincide. CoRR abs/1204.6291 (2012)
- 2011
- [j45]Martin Grohe: From polynomial time queries to graph structure theory. Commun. ACM 54(6): 104-112 (2011)
- [j44]Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory. Logical Methods in Computer Science 7(3) (2011)
- [c70]Martin Grohe, Berit Grußien, André Hernich, Bastian Laubner: L-Recursion and a new Logic for Logarithmic Space. CSL 2011: 277-291
- [c69]Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan: Finding topological subgraphs is fixed-parameter tractable. STOC 2011: 479-488
- [i19]Martin Grohe, Marc Thurley: Counting Homomorphisms and Partition Functions. CoRR abs/1104.0185 (2011)
- [i18]Martin Grohe, Dániel Marx: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs. CoRR abs/1111.1109 (2011)
- [i17]Martin Grohe, Michal Koucký, Rüdiger Reischuk, Dieter van Melkebeek: Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121). Dagstuhl Reports 1(3): 42-66 (2011)
- 2010
- [j43]Hubie Chen, Martin Grohe: Constraint satisfaction with succinctly specified relations. J. Comput. Syst. Sci. 76(8): 847-860 (2010)
- [j42]Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A Complexity Dichotomy for Partition Functions with Mixed Signs. SIAM J. Comput. 39(7): 3336-3402 (2010)
- [c68]Martin Grohe: Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs. Fields of Logic and Computation 2010: 328-353
- [c67]Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory. CSL 2010: 275-289
- [c66]
- [c65]Martin Grohe: Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors. LICS 2010: 179-188
- [i16]Martin Grohe: Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs. CoRR abs/1001.2572 (2010)
- [i15]Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan: Finding topological subgraphs is fixed-parameter tractable. CoRR abs/1011.1827 (2010)
- [i14]Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory. Electronic Colloquium on Computational Complexity (ECCC) 17: 56 (2010)
2000 – 2009
- 2009
- [j41]Martin Grohe, Götz Schwandtner: The Complexity of Datalog on Linear Orders. Logical Methods in Computer Science 5(1) (2009)
- [j40]Martin Grohe, André Hernich, Nicole Schweikardt: Lower bounds for processing data with few random accesses to external memory. J. ACM 56(3) (2009)
- [j39]Martin Grohe, Dániel Marx: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009)
- [j38]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)
- [c64]
- [c63]Anuj Dawar, Martin Grohe, Bjarki Holm, Bastian Laubner: Logics with Rank Operators. LICS 2009: 113-122
- [c62]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating Homomorphisms. STACS 2009: 231-242
- [c61]Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A Complexity Dichotomy for Partition Functions with Mixed Signs. STACS 2009: 493-504
- [i13]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating Homomorphisms. CoRR abs/0902.1256 (2009)
- 2008
- [j37]Albert Atserias, Anuj Dawar, Martin Grohe: Preservation under Extensions on Well-Behaved Finite Structures. SIAM J. Comput. 38(4): 1364-1381 (2008)
- [c60]
- [c59]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
- [c58]Albert Atserias, Martin Grohe, Dániel Marx: Size Bounds and Query Plans for Relational Joins. FOCS 2008: 739-748
- [c57]Manuel Bodirsky, Martin Grohe: Non-dichotomies in Constraint Satisfaction Complexity. ICALP (2) 2008: 184-196
- [c56]
- [c55]
- [c54]
- [c53]
- [e2]Martin Grohe, Rolf Niedermeier (Eds.): Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings. Lecture Notes in Computer Science 5018, Springer 2008, ISBN 978-3-540-79722-7
- [i12]Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A complexity dichotomy for partition functions with mixed signs. CoRR abs/0804.1932 (2008)
- 2007
- [j36]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)
- [j35]Isolde Adler, Georg Gottlob, Martin Grohe: Hypertree width and related hypergraph invariants. Eur. J. Comb. 28(8): 2167-2181 (2007)
- [j34]Martin Grohe: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1) (2007)
- [j33]Yijia Chen, Jörg Flum, Martin Grohe: An analysis of the W*-hierarchy. J. Symb. Log. 72(2): 513-534 (2007)
- [j32]Yijia Chen, Martin Grohe: An Isomorphism Between Subexponential and Parameterized Complexity Theory. SIAM J. Comput. 37(4): 1228-1258 (2007)
- [j31]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)
- [c52]Martin Grohe, Martin Hyland, Johann A. Makowsky, Damian Niwinski: The Ackermann Award 2007. CSL 2007: 589-597
- [c51]Martin Grohe, Magdalena Grüber: Parameterized Approximability of the Disjoint Cycle Problem. ICALP 2007: 363-374
- [c50]Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt: Model Theory Makes Formulas Large. ICALP 2007: 913-924
- [c49]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
- [c48]
- [i11]Martin Grohe, André Hernich, Nicole Schweikardt: Randomized Computations on Large Data Sets: Tight Lower Bounds. CoRR abs/cs/0703081 (2007)
- [i10]Martin Grohe: Logic, Graphs, and Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 14(091) (2007)
- [i9]Yijia Chen, Martin Grohe, Magdalena Grüber: On Parameterized Approximability. Electronic Colloquium on Computational Complexity (ECCC) 14(106) (2007)
- 2006
- [j30]Jörg Flum, Martin Grohe, Mark Weyer: Bounded fixed-parameter tractability and log2n nondeterministic bits. J. Comput. Syst. Sci. 72(1): 34-71 (2006)
- [c47]Yijia Chen, Martin Grohe: An Isomorphism between Subexponential and Parameterized Complexity Theory. IEEE Conference on Computational Complexity 2006: 314-330
- [c46]Hubie Chen, Martin Grohe: Constraint Satisfaction with Succinctly Specified Relations. Complexity of Constraints 2006
- [c45]Martin Grohe, Oleg Verbitsky: Testing Graph Isomorphism in Parallel by Playing a Game. ICALP (1) 2006: 3-14
- [c44]
- [c43]Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt: Approximation Schemes for First-Order Definable Optimisation Problems. LICS 2006: 411-420
- [c42]
- [c41]Martin Grohe, André Hernich, Nicole Schweikardt: Randomized computations on large data sets: tight lower bounds. PODS 2006: 243-252
- [c40]
- [e1]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger (Eds.): Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005. Dagstuhl Seminar Proceedings 05301, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2006
- [i8]Martin Grohe, Oleg Verbitsky: Testing Graph Isomorphism in Parallel by Playing a Game. CoRR abs/cs/0603054 (2006)
- [i7]Yijia Chen, Martin Grohe: An Isomorphism between Subexponential and Parameterized Complexity Theory. Electronic Colloquium on Computational Complexity (ECCC)(011) (2006)
- 2005
- [j29]Jörg Flum, Martin Grohe: Model-checking problems as a basis for parameterized intractability. Logical Methods in Computer Science 1(1) (2005)
- [j28]Martin Grohe, Nicole Schweikardt: The succinctness of first-order logic on linear orders. Logical Methods in Computer Science 1(1) (2005)
- [j27]Yijia Chen, Jörg Flum, Martin Grohe: Machine-based methods in parameterized complexity theory. Theor. Comput. Sci. 339(2-3): 167-199 (2005)
- [j26]Andrei A. Bulatov, Martin Grohe: The complexity of partition functions. Theor. Comput. Sci. 348(2-3): 148-186 (2005)
- [c39]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger: 05301 Summary - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability 2005
- [c38]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger: 05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability 2005
- [c37]Martin Grohe, Christoph Koch, Nicole Schweikardt: The Complexity of Querying External Memory and Streaming Data. FCT 2005: 1-16
- [c36]Martin Grohe, Christoph Koch, Nicole Schweikardt: Tight Lower Bounds for Query Processing on Streaming and External Memory Data. ICALP 2005: 1076-1088
- [c35]Albert Atserias, Anuj Dawar, Martin Grohe: Preservation Under Extensions on Well-Behaved Finite Structures. ICALP 2005: 1437-1449
- [c34]Martin Grohe, Stephan Kreutzer, Nicole Schweikardt: The Expressive Power of Two-Variable Least Fixed-Point Logics. MFCS 2005: 422-434
- [c33]Martin Grohe, Nicole Schweikardt: Lower bounds for sorting with few random accesses to external memory. PODS 2005: 238-249
- [c32]Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, Francesco Scarcello: Hypertree Decompositions: Structure, Algorithms, and Applications. WG 2005: 1-15
- [i6]Jörg Flum, Martin Grohe: Model-Checking Problems as a Basis for Parameterized Intractability. CoRR abs/cs/0502005 (2005)
- [i5]Martin Grohe, Nicole Schweikardt: The succinctness of first-order logic on linear orders. CoRR abs/cs/0502047 (2005)
- [i4]Martin Grohe, Christoph Koch, Nicole Schweikardt: Tight Lower Bounds for Query Processing on Streaming and External Memory Data. CoRR abs/cs/0505002 (2005)
- 2004
- [j25]Martin Grohe, Stefan Wöhrle: An existential locality theorem. Ann. Pure Appl. Logic 129(1-3): 131-148 (2004)
- [j24]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)
- [j23]Jörg Flum, Martin Grohe: Parametrized Complexity and Subexponential Time (Column: Computational Complexity). Bulletin of the EATCS 84: 71-100 (2004)
- [j22]Martin Grohe, Nicole Schweikardt: Comparing the succinctness of monadic query languages over finite trees. ITA 38(4): 343-373 (2004)
- [j21]Martin Grohe: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2): 285-302 (2004)
- [j20]Martin Grohe, György Turán: Learnability and Definability in Trees and Similar Structures. Theory Comput. Syst. 37(1): 193-220 (2004)
- [j19]Jörg Flum, Martin Grohe: The Parameterized Complexity of Counting Problems. SIAM J. Comput. 33(4): 892-922 (2004)
- [c31]
- [c30]Jörg Flum, Martin Grohe, Mark Weyer: Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits. ICALP 2004: 555-567
- [c29]
- [c28]Martin Grohe, Nicole Schweikardt: The Succinctness of First-Order Logic on Linear Orders. LICS 2004: 438-447
- 2003
- [j18]Martin Grohe: Local Tree-Width, Excluded Minors, and Approximation Algorithms. Combinatorica 23(4): 613-632 (2003)
- [j17]Jörg Flum, Martin Grohe: Describing parameterized complexity classes. Inf. Comput. 187(2): 291-319 (2003)
- [j16]Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin: Reachability and connectivity queries in constraint databases. J. Comput. Syst. Sci. 66(1): 169-206 (2003)
- [c27]Yijia Chen, Jörg Flum, Martin Grohe: Bounded Nondeterminism and Alternation in Parameterized Complexity Theory. IEEE Conference on Computational Complexity 2003: 13-29
- [c26]Martin Grohe, Nicole Schweikardt: Comparing the Succinctness of Monadic Query Languages over Finite Trees. CSL 2003: 226-240
- [c25]Martin Grohe: The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side. FOCS 2003: 552-561
- [c24]Markus Frick, Martin Grohe, Christoph Koch: Query Evaluation on Compressed Trees (Extended Abstract). LICS 2003: 188-
- [c23]
- 2002
- [j15]
- [j14]Jörg Flum, Markus Frick, Martin Grohe: Query evaluation via tree-decompositions. J. ACM 49(6): 716-752 (2002)
- [j13]
- [j12]Martin Grohe, Luc Segoufin: On first-order topological queries. ACM Trans. Comput. Log. 3(3): 336-358 (2002)
- [c22]
- [c21]Markus Frick, Martin Grohe: The Complexity of First-Order and Monadic Second-Order Logic Revisited. LICS 2002: 215-224
- [c20]
- [c19]Martin Grohe, György Turán: Learnability and Definability in Trees and Similar Structures. STACS 2002: 645-658
- 2001
- [j11]Markus Frick, Martin Grohe: Deciding first-order properties of locally tree-decomposable structures. J. ACM 48(6): 1184-1206 (2001)
- [j10]Jörg Flum, Martin Grohe: Fixed-Parameter Tractability, Definability, and Model-Checking. SIAM J. Comput. 31(1): 113-145 (2001)
- [c18]
- [c17]
- [c16]
- [c15]
- [c14]
- [c13]Martin Grohe, Thomas Schwentick, Luc Segoufin: When is the evaluation of conjunctive queries tractable? STOC 2001: 657-666
- 2000
- [j9]
- [j8]Martin Grohe, Thomas Schwentick: Locality of order-invariant first-order formulas. ACM Trans. Comput. Log. 1(1): 112-130 (2000)
- [c12]
- [c11]Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin: Reachability and Connectivity Queries in Constraint Databases. PODS 2000: 104-115
- [c10]
- [i3]Markus Frick, Martin Grohe: Deciding first-order properties of locally tree-decomposable structures. CoRR cs.DS/0004007 (2000)
- [i2]
1990 – 1999
- 1999
- [j7]Martin Grohe: Equivalence in Finite-Variable Logics is Complete for Polynomial Time. Combinatorica 19(4): 507-532 (1999)
- [c9]
- [c8]Markus Frick, Martin Grohe: Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs. ICALP 1999: 331-340
- [c7]Martin Grohe, Julian Mariño: Definability and Descriptive Complexity on Databases of Bounded Tree-Width. ICDT 1999: 70-82
- [i1]Jörg Flum, Martin Grohe: Fixed-parameter tractability, definability, and model checking. CoRR cs.CC/9910001 (1999)
- 1998
- [j6]Martin Grohe: Finite variable logics in descriptive complexity theory. Bulletin of Symbolic Logic 4(4): 345-398 (1998)
- [c6]
- [c5]Martin Grohe, Thomas Schwentick: Locality of Order-Invariant First-Order Formulas. MFCS 1998: 437-445
- 1997
- [j5]Martin Grohe: Existential Least Fixed-Point Logic and its Relatives. J. Log. Comput. 7(2): 205-228 (1997)
- [c4]
- [c3]
- 1996
- [j4]Martin Grohe, Lauri Hella: A double arity hierarchy theorem for transitive closure logic. Arch. Math. Log. 35(3): 157-171 (1996)
- [j3]
- [j2]
- [c2]Martin Grohe: Equivalence in Finite-Variable Logics is Complete for Polynomial Time. FOCS 1996: 264-273
- 1995
- [j1]
- 1993
- [c1]
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:09 CEST by the dblp team