Martin Grohe

	2012
140		Martin Grohe: Structural and logical approaches to the graph isomorphism problem. SODA 2012: 188
139		Martin Grohe, Dániel Marx: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. STOC 2012: 173-192
138		Martin Grohe, Martin Otto: Pebble Games and Linear Equations CoRR abs/1204.1990: (2012)
137		Michael Elberfeld, Martin Grohe, Till Tantau: Where First-Order and Monadic Second-Order Logic Coincide CoRR abs/1204.6291: (2012)
136		Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating homomorphisms. J. Comput. Syst. Sci. 78(2): 638-650 (2012)
	2011
135		Martin Grohe, Berit Grußien, André Hernich, Bastian Laubner: L-Recursion and a new Logic for Logarithmic Space. CSL 2011: 277-291
134		Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan: Finding topological subgraphs is fixed-parameter tractable. STOC 2011: 479-488
133		Martin Grohe, Marc Thurley: Counting Homomorphisms and Partition Functions CoRR abs/1104.0185: (2011)
132		Martin Grohe, Dániel Marx: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs CoRR abs/1111.1109: (2011)
131		Martin Grohe: From polynomial time queries to graph structure theory. Commun. ACM 54(6): 104-112 (2011)
130		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)
129		Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory Logical Methods in Computer Science 7(3): (2011)
	2010
128		Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory. CSL 2010: 275-289
127		Martin Grohe: Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs. Fields of Logic and Computation 2010: 328-353
126		Martin Grohe: From polynomial time queries to graph structure theory. ICDT 2010: 2
125		Martin Grohe: Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors. LICS 2010: 179-188
124		Martin Grohe: Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs CoRR abs/1001.2572: (2010)
123		Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan: Finding topological subgraphs is fixed-parameter tractable CoRR abs/1011.1827: (2010)
122		Kord Eickmeyer, Martin Grohe: Randomisation and Derandomisation in Descriptive Complexity Theory. Electronic Colloquium on Computational Complexity (ECCC) 17: 56 (2010)
121		Hubie Chen, Martin Grohe: Constraint satisfaction with succinctly specified relations. J. Comput. Syst. Sci. 76(8): 847-860 (2010)
120		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)
	2009
119		Martin Grohe: Fixed-Point Definability and Polynomial Time. CSL 2009: 20-23
118		Anuj Dawar, Martin Grohe, Bjarki Holm, Bastian Laubner: Logics with Rank Operators. LICS 2009: 113-122
117		Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating Homomorphisms. STACS 2009: 231-242
116		Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A Complexity Dichotomy for Partition Functions with Mixed Signs. STACS 2009: 493-504
115		Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating Homomorphisms CoRR abs/0902.1256: (2009)
114		Martin Grohe, André Hernich, Nicole Schweikardt: Lower bounds for processing data with few random accesses to external memory. J. ACM 56(3): (2009)
113		Martin Grohe, Dániel Marx: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009)
112		Martin Grohe, Götz Schwandtner: The Complexity of Datalog on Linear Orders Logical Methods in Computer Science 5(1): (2009)
111		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
110		Martin Grohe, Rolf Niedermeier: Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings Springer 2008
109		Albert Atserias, Martin Grohe, Dániel Marx: Size Bounds and Query Plans for Relational Joins. FOCS 2008: 739-748
108		Manuel Bodirsky, Martin Grohe: Non-dichotomies in Constraint Satisfaction Complexity. ICALP (2) 2008: 184-196
107		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
106		Martin Grohe: The Quest for a Logic Capturing PTIME. LICS 2008: 267-271
105		Martin Grohe: Definable Tree Decompositions. LICS 2008: 406-417
104		Martin Grohe: Logic, graphs, and algorithms. Logic and Automata 2008: 357-422
103		Isolde Adler, Martin Grohe, Stephan Kreutzer: Computing excluded minors. SODA 2008: 641-650
102		Martin Grohe: Algorithmic Meta Theorems. WG 2008: 30
101		Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley: A complexity dichotomy for partition functions with mixed signs CoRR abs/0804.1932: (2008)
100		Albert Atserias, Anuj Dawar, Martin Grohe: Preservation under Extensions on Well-Behaved Finite Structures. SIAM J. Comput. 38(4): 1364-1381 (2008)
	2007
99		Martin Grohe, Martin Hyland, Johann A. Makowsky, Damian Niwinski: The Ackermann Award 2007. CSL 2007: 589-597
98		Martin Grohe, Magdalena Grüber: Parameterized Approximability of the Disjoint Cycle Problem. ICALP 2007: 363-374
97		Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt: Model Theory Makes Formulas Large. ICALP 2007: 913-924
96		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
95		Anuj Dawar, Martin Grohe, Stephan Kreutzer: Locally Excluding a Minor. LICS 2007: 270-279
94		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)
93		Martin Grohe, André Hernich, Nicole Schweikardt: Randomized Computations on Large Data Sets: Tight Lower Bounds CoRR abs/cs/0703081: (2007)
92		Martin Grohe: Logic, Graphs, and Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 14(091): (2007)
91		Yijia Chen, Martin Grohe, Magdalena Grüber: On Parameterized Approximability. Electronic Colloquium on Computational Complexity (ECCC) 14(106): (2007)
90		Isolde Adler, Georg Gottlob, Martin Grohe: Hypertree width and related hypergraph invariants. Eur. J. Comb. 28(8): 2167-2181 (2007)
89		Martin Grohe: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1): (2007)
88		Yijia Chen, Jörg Flum, Martin Grohe: An analysis of the W*-hierarchy. J. Symb. Log. 72(2): 513-534 (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

Coauthor Index

1	Isolde Adler	[90] [103]
2	Albert Atserias	[69] [100] [109]
3	Michael Benedikt	[22] [40]
4	Manuel Bodirsky	[108]
5	Andrei A. Bulatov	[58] [59] [115] [117] [136]
6	Peter Buneman	[43]
7	Jan Van den Bussche	[96] [111]
8	Hubie Chen	[84] [121]
9	Yijia Chen	[45] [60] [75] [81] [82] [87] [88] [91]
10	Víctor Dalmau	[115] [117] [136]
11	Anuj Dawar	[69] [80] [95] [97] [100] [118]
12	Rodney G. Downey (Rod Downey)	[72] [73] [85] [94]
13	Kord Eickmeyer	[107] [122] [128] [129]
14	Michael Elberfeld	[137]
15	Jörg Flum	[13] [17] [24] [30] [33] [37] [39] [41] [45] [49] [52] [56] [57] [60] [62] [65] [74] [88] [94]
16	Markus Frick	[15] [19] [25] [30] [33] [38] [44] [53]
17	Leslie Ann Goldberg	[101] [116] [120]
18	Georg Gottlob	[66] [90]
19	Magdalena Grüber	[81] [91] [98] [107]
20	Berit Grußien	[135]
21	Yuri Gurevich	[96] [111]
22	André Hernich	[78] [93] [114] [135]
23	Bjarki Holm	[118]
24	Martin Hyland (J. M. E. Hyland)	[99]
25	Mark Jerrum	[101] [116] [120]
26	Ken-ichi Kawarabayashi	[123] [134]
27	Christoph Koch	[43] [44] [63] [70] [71] [86]
28	Michal Koucký	[130]
29	Stephan Kreutzer	[68] [80] [95] [97] [103]
30	Bastian Laubner	[118] [135]
31	Dirk Leinders	[96] [111]
32	Leonid Libkin	[22] [40]
33	Johann A. Makowsky (Janos Makowsky)	[99]
34	Julian Mariño	[14]
35	Dániel Marx	[77] [109] [113] [115] [117] [123] [132] [134] [136] [139]
36	Dieter van Melkebeek	[130]
37	Nysret Musliu	[66]
38	Rolf Niedermeier	[110]
39	Damian Niwinski	[99]
40	Martin Otto	[138]
41	Rüdiger Reischuk	[130]
42	Marko Samer	[66]
43	Francesco Scarcello	[66]
44	Götz Schwandtner	[112]
45	Nicole Schweikardt	[47] [51] [55] [61] [63] [64] [67] [68] [70] [71] [78] [80] [86] [93] [96] [97] [111] [114]
46	Thomas Schwentick	[10] [20] [26]
47	Luc Segoufin	[22] [23] [26] [35] [40]
48	Till Tantau	[137]
49	Marc Thurley	[101] [116] [120] [133]
50	György Turán	[36] [48]
51	Jerzy Tyszkiewicz	[96] [111]
52	Oleg Verbitsky	[76] [83]
53	Mark Weyer	[57] [74] [94]
54	Gerhard J. Woeginger	[72] [73] [85]
55	Stefan Wöhrle	[31] [54]
56	Paul Wollan	[123] [134]

Colors in the list of coauthors

Last update Fri May 25 01:42:58 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page