![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Martin Grohe
Person information
- affiliation: RWTH Aachen University, Germany
Refine list
![note](https://dblp1.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j75]Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, Martin Grohe:
Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. Trans. Mach. Learn. Res. 2024 (2024) - [j74]Nofar Carmeli
, Martin Grohe
, Benny Kimelfeld
, Ester Livshits
, Muhammad Tibi
:
Database Repairing with Soft Functional Dependencies. ACM Trans. Database Syst. 49(2): 8:1-8:34 (2024) - [c143]Martin Grohe, Daniel Neuen:
Isomorphism for Tournaments of Small Twin Width. ICALP 2024: 78:1-78:20 - [c142]Martin Grohe, Benny Kimelfeld, Peter Lindner, Christoph Standke:
The Importance of Parameters in Database Queries. ICDT 2024: 14:1-14:17 - [c141]Martin Grohe
, Eran Rosenbluth
:
Are Targeted Messages More Effective? LICS 2024: 40:1-40:14 - [c140]Martin Grohe
, Jan Van den Bussche
, Ke Yi
:
The ACM PODS Alberto O. Mendelzon Test-of-Time Award 2024. PODS Companion 2024: 7 - [e7]Karl Bringmann
, Martin Grohe
, Gabriele Puppis
, Ola Svensson
:
51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia. LIPIcs 297, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-322-5 [contents] - [i103]Martin Grohe, Benny Kimelfeld, Peter Lindner, Christoph Standke:
The Importance of Parameters in Database Queries. CoRR abs/2401.04606 (2024) - [i102]Yuval Lev Lubarsky, Jan Tönshoff, Martin Grohe, Benny Kimelfeld:
Selecting Walk Schemes for Database Embedding. CoRR abs/2401.11215 (2024) - [i101]Christopher Morris, Nadav Dym, Haggai Maron, Ismail Ilkan Ceylan, Fabrizio Frasca, Ron Levie, Derek Lim, Michael M. Bronstein, Martin Grohe, Stefanie Jegelka:
Future Directions in Foundations of Graph Machine Learning. CoRR abs/2402.02287 (2024) - [i100]Martin Grohe, Eran Rosenbluth:
Are Targeted Messages More Effective? CoRR abs/2403.06817 (2024) - [i99]Hinrikus Wolf, Luis Böttcher, Sarra Bouchkati, Philipp Lutat, Jens Breitung, Bastian Jung, Tina Möllemann, Viktor Todosijevic, Jan Schiefelbein-Lach, Oliver Pohl, Andreas Ulbig, Martin Grohe:
End-to-End Reinforcement Learning of Curative Curtailment with Partial Measurement Availability. CoRR abs/2405.03262 (2024) - [i98]Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, Martin Grohe:
Distinguished In Uniform: Self Attention Vs. Virtual Nodes. CoRR abs/2405.11951 (2024) - 2023
- [j73]Artur M. Schweidtmann
, Jan G. Rittig
, Jana M. Weber
, Martin Grohe
, Manuel Dahmen
, Kai Leonhard
, Alexander Mitsos
:
Physical pooling functions in graph neural networks for molecular property prediction. Comput. Chem. Eng. 172: 108202 (2023) - [j72]Martin Grohe, Daniel Neuen
, Daniel Wiebking:
Isomorphism Testing for Graphs Excluding Small Minors. SIAM J. Comput. 52(1): 238-272 (2023) - [j71]Martin Grohe, Daniel Neuen, Pascal Schweitzer
:
A Faster Isomorphism Test for Graphs of Small Degree. SIAM J. Comput. 52(6): S18-1 (2023) - [j70]Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, Martin Grohe:
Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing. Trans. Mach. Learn. Res. 2023 (2023) - [j69]Martin Grohe
, Daniel Neuen
:
Canonisation and Definability for Graphs of Bounded Rank Width. ACM Trans. Comput. Log. 24(1): 6:1-6:31 (2023) - [c139]Yuval Lev Lubarsky
, Jan Tönshoff
, Martin Grohe
, Benny Kimelfeld
:
Selecting Walk Schemes for Database Embedding. CIKM 2023: 1677-1686 - [c138]Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer
:
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. FOCS 2023: 798-809 - [c137]Jan Tönshoff, Neta Friedman, Martin Grohe, Benny Kimelfeld:
Stable Tuple Embeddings for Dynamic Databases. ICDE 2023: 1286-1299 - [c136]Martin Grohe, Peter Lindner, Christoph Standke:
Probabilistic Query Evaluation with Bag Semantics. ICDT 2023: 20:1-20:19 - [c135]Christopher Morris, Floris Geerts, Jan Tönshoff, Martin Grohe:
WL meet VC. ICML 2023: 25275-25302 - [c134]Eran Rosenbluth, Jan Tönshoff, Martin Grohe:
Some Might Say All You Need Is Sum. IJCAI 2023: 4172-4179 - [c133]Jan Tönshoff, Berke Kisin, Jakob Lindner, Martin Grohe:
One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction. IJCAI 2023: 4280-4288 - [c132]Steffen van Bergerem
, Martin Grohe, Sandra Kiefer
, Luca Oeljeklaus:
Simulating Logspace-Recursion with Logarithmic Quantifier Depth. LICS 2023: 1-13 - [c131]Martin Grohe:
The Descriptive Complexity of Graph Neural Networks. LICS 2023: 1-14 - [c130]Martin Grohe, Moritz Lichter, Daniel Neuen
:
The Iteration Number of the Weisfeiler-Leman Algorithm. LICS 2023: 1-13 - [d1]Artur M. Schweidtmann
, Jan G. Rittig
, Jana M. Weber
, Martin Grohe
, Manuel Dahmen, Kai Leonhard
, Alexander Mitsos
:
Software for "Physical Pooling Functions in Graph Neural Networks for Molecular Property Prediction". Zenodo, 2023 - [i97]Christopher Morris, Floris Geerts, Jan Tönshoff, Martin Grohe:
WL meet VC. CoRR abs/2301.11039 (2023) - [i96]Martin Grohe, Moritz Lichter, Daniel Neuen:
The Iteration Number of the Weisfeiler-Leman Algorithm. CoRR abs/2301.13317 (2023) - [i95]Eran Rosenbluth, Jan Tönshoff, Martin Grohe:
Some Might Say All You Need Is Sum. CoRR abs/2302.11603 (2023) - [i94]Martin Grohe:
The Descriptive Complexity of Graph Neural Networks. CoRR abs/2303.04613 (2023) - [i93]Steffen van Bergerem, Martin Grohe, Sandra Kiefer
, Luca Oeljeklaus:
Simulating Logspace-Recursion with Logarithmic Quantifier Depth. CoRR abs/2304.12948 (2023) - [i92]Martin Grohe, Moritz Lichter, Daniel Neuen
, Pascal Schweitzer
:
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements. CoRR abs/2308.11970 (2023) - [i91]Hinrikus Wolf, Luca Oeljeklaus, Pascal Kühner, Martin Grohe:
Structural Node Embeddings with Homomorphism Counts. CoRR abs/2308.15283 (2023) - [i90]Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, Martin Grohe:
Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. CoRR abs/2309.00367 (2023) - [i89]Steffen van Bergerem, Martin Grohe, Nina Runde:
On the Parameterized Complexity of Learning Monadic Second-Order Formulas. CoRR abs/2309.10489 (2023) - [i88]Martin Grohe, Daniel Neuen
:
Isomorphism for Tournaments of Small Twin Width. CoRR abs/2312.02048 (2023) - 2022
- [j68]Martin Grohe
, Peter Lindner
:
Independence in Infinite Probabilistic Databases. J. ACM 69(5): 37:1-37:42 (2022) - [j67]Martin Grohe
, Benjamin Lucien Kaminski
, Joost-Pieter Katoen
, Peter Lindner
:
Generative Datalog with Continuous Distributions. J. ACM 69(6): 46:1-46:52 (2022) - [j66]Martin Grohe, Peter Lindner:
Infinite Probabilistic Databases. Log. Methods Comput. Sci. 18(1) (2022) - [c129]Martin Grohe, Gaurav Rattan
, Tim Seppelt
:
Homomorphism Tensors and Linear Equations. ICALP 2022: 70:1-70:20 - [c128]Timo Gervens
, Martin Grohe
:
Graph Similarity Based on Matrix Norms. MFCS 2022: 52:1-52:15 - [c127]Steffen van Bergerem
, Martin Grohe, Martin Ritzert:
On the Parameterized Complexity of Learning First-Order Logic. PODS 2022: 337-346 - [i87]Martin Grohe, Peter Lindner, Christoph Standke:
Probabilistic Query Evaluation with Bag Semantics. CoRR abs/2201.11524 (2022) - [i86]Luis Böttcher, Hinrikus Wolf, Bastian Jung, Philipp Lutat, Marc Trageser, Oliver Pohl, Andreas Ulbig, Martin Grohe:
Solving AC Power Flow with Graph Neural Networks under Realistic Constraints. CoRR abs/2204.07000 (2022) - [i85]Jan G. Rittig, Martin Ritzert, Artur M. Schweidtmann
, Stefanie Winkler, Jana M. Weber, Philipp Morsch, K. Alexander Heufer, Martin Grohe, Alexander Mitsos, Manuel Dahmen:
Graph Machine Learning for Design of High-Octane Fuels. CoRR abs/2206.00619 (2022) - [i84]Timo Gervens, Martin Grohe:
Graph Similarity Based on Matrix Norms. CoRR abs/2207.00090 (2022) - [i83]Artur M. Schweidtmann
, Jan G. Rittig, Jana M. Weber, Martin Grohe, Manuel Dahmen, Kai Leonhard, Alexander Mitsos:
Physical Pooling Functions in Graph Neural Networks for Molecular Property Prediction. CoRR abs/2207.13779 (2022) - [i82]Jan Tönshoff, Berke Kisin, Jakob Lindner, Martin Grohe:
One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction. CoRR abs/2208.10227 (2022) - [i81]Martin Grohe, Stephan Günnemann, Stefanie Jegelka, Christopher Morris:
Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132). Dagstuhl Reports 12(3): 141-155 (2022) - [i80]Martin Grohe, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). Dagstuhl Reports 12(5): 112-130 (2022) - 2021
- [j65]Martin Grohe, Daniel Neuen
:
Isomorphism, canonization, and definability for graphs of bounded rank width. Commun. ACM 64(5): 98-105 (2021) - [j64]Mikolaj Bojanczyk, Martin Grohe, Michal Pilipczuk:
Definable decompositions for graphs of bounded linear cliquewidth. Log. Methods Comput. Sci. 17(1) (2021) - [j63]Martin Grohe, Benjamin Lucien Kaminski
, Joost-Pieter Katoen, Peter Lindner:
Probabilistic Data with Continuous Distributions. SIGMOD Rec. 50(1): 69-76 (2021) - [c126]Martin Grohe, Daniel Neuen:
Recent advances on the graph isomorphism problem. BCC 2021: 187-234 - [c125]Martin Grohe, Sandra Kiefer
:
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. ICALP 2021: 134:1-134:20 - [c124]Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, Muhammad Tibi:
Database Repairing with Soft Functional Dependencies. ICDT 2021: 16:1-16:17 - [c123]Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, Thomas Lukasiewicz:
The Surprising Power of Graph Neural Networks with Random Node Initialization. IJCAI 2021: 2112-2118 - [c122]Martin Grohe:
The Logic of Graph Neural Networks. LICS 2021: 1-17 - [c121]Martin Grohe:
A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). MFCS 2021: 2:1-2:1 - [c120]Tobias Schumacher
, Hinrikus Wolf
, Martin Ritzert
, Florian Lemmerich
, Martin Grohe
, Markus Strohmaier
:
The Effects of Randomness on the Stability of Node Embeddings. PKDD/ECML Workshops (1) 2021: 197-215 - [c119]Nofar Carmeli, Martin Grohe, Peter Lindner, Christoph Standke:
Tuple-Independent Representations of Infinite Probabilistic Databases. PODS 2021: 388-401 - [c118]Martin Grohe, Pascal Schweitzer, Daniel Wiebking:
Deep Weisfeiler Leman. SODA 2021: 2600-2614 - [i79]Martin Grohe, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Peter Lindner:
Probabilistic Data with Continuous Distributions. CoRR abs/2101.12289 (2021) - [i78]Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, Martin Grohe:
Graph Learning with 1D Convolutions on Random Walks. CoRR abs/2102.08786 (2021) - [i77]Steffen van Bergerem, Martin Grohe, Martin Ritzert:
On the Parameterized Complexity of Learning Logic. CoRR abs/2102.12201 (2021) - [i76]Jan Tönshoff, Neta Friedman, Martin Grohe, Benny Kimelfeld:
Dynamic Database Embeddings with FoRWaRD. CoRR abs/2103.06766 (2021) - [i75]Martin Grohe:
The Logic of Graph Neural Networks. CoRR abs/2104.14624 (2021) - [i74]Martin Grohe, Sandra Kiefer:
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. CoRR abs/2106.16218 (2021) - [i73]Martin Grohe, Gaurav Rattan, Tim Seppelt:
Homomorphism Tensors and Linear Equations. CoRR abs/2111.11313 (2021) - [i72]Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, Karsten M. Borgwardt:
Weisfeiler and Leman go Machine Learning: The Story so far. CoRR abs/2112.09992 (2021) - 2020
- [j62]Martin Grohe, Pascal Schweitzer
:
The graph isomorphism problem. Commun. ACM 63(11): 128-134 (2020) - [j61]Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, Martin Grohe:
Graph Neural Networks for Maximum Constraint Satisfaction. Frontiers Artif. Intell. 3: 580607 (2020) - [j60]Martin Grohe, Daniel Neuen
, Pascal Schweitzer
, Daniel Wiebking:
An Improved Isomorphism Test for Bounded-tree-width Graphs. ACM Trans. Algorithms 16(3): 34:1-34:31 (2020) - [c117]Martin Grohe, Daniel Wiebking, Daniel Neuen
:
Isomorphism Testing for Graphs Excluding Small Minors. FOCS 2020: 625-636 - [c116]Martin Grohe
, Peter Lindner
:
Infinite Probabilistic Databases. ICDT 2020: 16:1-16:20 - [c115]Martin Grohe:
Counting Bounded Tree Depth Homomorphisms. LICS 2020: 507-520 - [c114]Martin Grohe:
word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data. PODS 2020: 1-16 - [c113]Martin Grohe, Benjamin Lucien Kaminski
, Joost-Pieter Katoen, Peter Lindner:
Generative Datalog with Continuous Distributions. PODS 2020: 347-360 - [c112]Martin Grohe
:
Weisfeiler and Leman's Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk). STACS 2020: 2:1-2:1 - [i71]Martin Grohe, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Peter Lindner:
Generative Datalog with Continuous Distributions. CoRR abs/2001.06358 (2020) - [i70]Martin Grohe:
Counting Bounded Tree Depth Homomorphisms. CoRR abs/2003.08164 (2020) - [i69]Martin Grohe, Pascal Schweitzer, Daniel Wiebking:
Deep Weisfeiler Leman. CoRR abs/2003.10935 (2020) - [i68]Martin Grohe:
word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data. CoRR abs/2003.12590 (2020) - [i67]Martin Grohe, Daniel Neuen, Daniel Wiebking:
Isomorphism Testing for Graphs Excluding Small Minors. CoRR abs/2004.07671 (2020) - [i66]Tobias Schumacher, Hinrikus Wolf, Martin Ritzert, Florian Lemmerich, Jan Bachmann, Florian Frantzen
, Max Klabunde, Martin Grohe, Markus Strohmaier:
The Effects of Randomness on the Stability of Node Embeddings. CoRR abs/2005.10039 (2020) - [i65]Nofar Carmeli, Martin Grohe, Peter Lindner, Christoph Standke:
Tuple-Independent Representations of Infinite Probabilistic Databases. CoRR abs/2008.09511 (2020) - [i64]Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, Muhammad Tibi:
Database Repairing with Soft Functional Dependencies. CoRR abs/2009.13821 (2020) - [i63]Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, Thomas Lukasiewicz:
The Surprising Power of Graph Neural Networks with Random Node Initialization. CoRR abs/2010.01179 (2020) - [i62]Martin Grohe, Peter Lindner:
Independence in Infinite Probabilistic Databases. CoRR abs/2011.00096 (2020) - [i61]Martin Grohe, Daniel Neuen:
Recent Advances on the Graph Isomorphism Problem. CoRR abs/2011.01366 (2020) - [i60]Martin Grohe, Peter Lindner:
Standard Probabilistic Databases. CoRR abs/2011.14860 (2020) - [i59]Martin Grohe, Pascal Schweitzer, Daniel Wiebking:
Automorphism groups of graphs of bounded Hadwiger number. CoRR abs/2012.14300 (2020)
2010 – 2019
- 2019
- [j59]Erich Grädel, Martin Grohe, Benedikt Pago, Wied Pakusa:
A Finite-Model-Theoretic View on Propositional Proof Complexity. Log. Methods Comput. Sci. 15(1) (2019) - [c111]Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan
, Martin Grohe:
Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. AAAI 2019: 4602-4609 - [c110]Martin Grohe
:
Symmetry and Similarity (Invited Talk). ICALP 2019: 2:1-2:1 - [c109]Martin Grohe, Sandra Kiefer
:
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus. ICALP 2019: 117:1-117:15 - [c108]Martin Grohe, Daniel Neuen
:
Canonisation and Definability for Graphs of Bounded Rank Width. LICS 2019: 1-13 - [c107]Jan Böker
, Yijia Chen
, Martin Grohe
, Gaurav Rattan
:
The Complexity of Homomorphism Indistinguishability. MFCS 2019: 54:1-54:13 - [c106]Martin Grohe, Peter Lindner:
Probabilistic Databases with an Infinite Open-World Assumption. PODS 2019: 17-31 - [i58]Martin Grohe, Daniel Neuen:
Canonisation and Definability for Graphs of Bounded Rank Width. CoRR abs/1901.10330 (2019) - [i57]Martin Grohe, Peter Lindner:
Infinite Probabilistic Databases. CoRR abs/1904.06766 (2019) - [i56]Martin Grohe, Sandra Kiefer:
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus. CoRR abs/1904.07216 (2019) - [i55]Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, Martin Grohe:
RUN-CSP: Unsupervised Learning of Message Passing Networks for Binary Constraint Satisfaction Problems. CoRR abs/1909.08387 (2019) - 2018
- [j58]Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz
, Konstantinos S. Stavropoulos:
Coloring and Covering Nowhere Dense Graphs. SIAM J. Discret. Math. 32(4): 2467-2481 (2018) - [c105]Martin Grohe, Daniel Neuen
, Pascal Schweitzer
:
A Faster Isomorphism Test for Graphs of Small Degree. FOCS 2018: 89-100 - [c104]Holger Dell, Martin Grohe, Gaurav Rattan
:
Lovász Meets Weisfeiler and Leman. ICALP 2018: 40:1-40:14 - [c103]Martin Grohe, Daniel Neuen
, Pascal Schweitzer
, Daniel Wiebking:
An Improved Isomorphism Test for Bounded-Tree-Width Graphs. ICALP 2018: 67:1-67:14 - [c102]Mikolaj Bojanczyk, Martin Grohe, Michal Pilipczuk
:
Definable decompositions for graphs of bounded linear cliquewidth. LICS 2018: 135-144 - [c101]Martin Grohe, Gaurav Rattan
, Gerhard J. Woeginger:
Graph Similarity and Approximate Isomorphism. MFCS 2018: 20:1-20:16 - [c100]Martin Grohe, Nicole Schweikardt:
First-Order Query Evaluation with Cardinality Conditions. PODS 2018: 253-266 - [i54]Martin Grohe, Daniel Neuen, Pascal Schweitzer:
Towards faster isomorphism tests for bounded-degree graphs. CoRR abs/1802.04659 (2018) - [i53]Martin Grohe, Gaurav Rattan, Gerhard J. Woeginger:
Graph Similarity and Approximate Isomorphism. CoRR abs/1802.08509 (2018) - [i52]Holger Dell, Martin Grohe, Gaurav Rattan:
Weisfeiler-Leman meets Homomorphisms. CoRR abs/1802.08876 (2018) - [i51]Erich Grädel, Martin Grohe, Benedikt Pago, Wied Pakusa:
A Finite-Model-Theoretic View on Propositional Proof Complexity. CoRR abs/1802.09377 (2018) - [i50]Mikolaj Bojanczyk, Martin Grohe, Michal Pilipczuk:
Definable decompositions for graphs of bounded linear cliquewidth. CoRR abs/1803.05937 (2018) - [i49]Martin Grohe, Daniel Neuen, Pascal Schweitzer, Daniel Wiebking:
An improved isomorphism test for bounded-tree-width graphs. CoRR abs/1803.06858 (2018) - [i48]Martin Grohe, Peter Lindner:
Probabilistic Databases with an Infinite Open-World Assumption. CoRR abs/1807.00607 (2018) - [i47]Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe:
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. CoRR abs/1810.02244 (2018) - [i46]Martin Grohe, Venkatesan Guruswami, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231). Dagstuhl Reports 8(6): 1-18 (2018) - 2017
- [b2]Martin Grohe:
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic 47, Cambridge University Press 2017, ISBN 9781139028868 - [j57]Martin Grohe
, Stephan Kreutzer, Sebastian Siebertz
:
Deciding First-Order Properties of Nowhere Dense Graphs. J. ACM 64(3): 17:1-17:32 (2017) - [j56]Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Theory Comput. Syst. 60(4): 581-614 (2017) - [c99]Martin Grohe, Christof Löding, Martin Ritzert:
Learning MSO-definable hypotheses on strings. ALT 2017: 434-451 - [c98]Martin Grohe, Wied Pakusa:
Descriptive complexity of linear equation systems and applications to propositional proof complexity. LICS 2017: 1-12 - [c97]Martin Grohe, Martin Ritzert:
Learning first-order definable concepts over structures of small degree. LICS 2017: 1-12 - [c96]Christoph Berkholz, Martin Grohe:
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. SODA 2017: 327-339 - [c95]Yijia Chen, Martin Grohe, Bingkai Lin
:
The Hardness of Embedding Grids and Walls. WG 2017: 180-192 - [i45]Martin Grohe, Martin Ritzert:
Learning first-order definable concepts over structures of small degree. CoRR abs/1701.05487 (2017) - [i44]Yijia Chen, Martin Grohe, Bingkai Lin:
The Hardness of Embedding Grids and Walls. CoRR abs/1703.06423 (2017) - [i43]Martin Grohe, Nicole Schweikardt:
First-Order Query Evaluation with Cardinality Conditions. CoRR abs/1707.05945 (2017) - [i42]Martin Grohe, Christof Löding, Martin Ritzert:
Learning MSO-definable hypotheses on string. CoRR abs/1708.08081 (2017) - [i41]Albert Atserias, Martin Grohe, Dániel Marx:
Size bounds and query plans for relational joins. CoRR abs/1711.03860 (2017) - [i40]Martin Grohe, Dániel Marx:
Constraint Solving via Fractional Edge Covers. CoRR abs/1711.04506 (2017) - 2016
- [j55]Martin Grohe, Pascal Schweitzer
:
Computing with Tangles. SIAM J. Discret. Math. 30(2): 1213-1247 (2016) - [j54]Michael Elberfeld, Martin Grohe, Till Tantau:
Where First-Order and Monadic Second-Order Logic Coincide. ACM Trans. Comput. Log. 17(4): 25 (2016) - [c94]Martin Grohe:
Quasi-4-Connected Components. ICALP 2016: 8:1-8:13 - [c93]Martin Grohe
:
Tangles and Connectivity in Graphs. LATA 2016: 24-41 - [c92]Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe:
Order Invariance on Decomposable Structures. LICS 2016: 397-406 - [e6]Martin Grohe, Eric Koskinen, Natarajan Shankar:
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016. ACM 2016, ISBN 978-1-4503-4391-6 [contents] - [i39]Martin Grohe:
Quasi-4-Connected Components. CoRR abs/1602.04505 (2016) - [i38]Martin Grohe:
Tangles and Connectivity in Graphs. CoRR abs/1602.04727 (2016) - [i37]Martin Grohe:
Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles). CoRR abs/1605.06704 (2016) - [i36]Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe:
Order Invariance on Decomposable Structures. CoRR abs/1606.06557 (2016) - [i35]Christoph Berkholz, Martin Grohe:
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. CoRR abs/1607.04287 (2016) - 2015
- [j53]Martin Grohe
, Martin Otto:
Pebble Games and linear equations. J. Symb. Log. 80(3): 797-844 (2015) - [j52]Martin Grohe
, Dániel Marx:
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs. SIAM J. Comput. 44(1): 114-159 (2015) - [c91]Erich Grädel, Martin Grohe
:
Is Polynomial Time Choiceless? Fields of Logic and Computation II 2015: 193-209 - [c90]Martin Grohe
, Pascal Schweitzer
:
Isomorphism Testing for Graphs of Bounded Rank Width. FOCS 2015: 1010-1029 - [c89]Christoph Berkholz, Martin Grohe
:
Limitations of Algebraic Approaches to Graph Isomorphism Testing. ICALP (1) 2015: 155-166 - [c88]Martin Grohe
, Pascal Schweitzer
:
Computing with Tangles. STOC 2015: 683-692 - [c87]Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz
, Konstantinos S. Stavropoulos:
Colouring and Covering Nowhere Dense Graphs. WG 2015: 325-338 - [i34]Christoph Berkholz, Martin Grohe:
Limitations of Algebraic Approaches to Graph Isomorphism Testing. CoRR abs/1502.05912 (2015) - [i33]Martin Grohe, Pascal Schweitzer:
Computing with Tangles. CoRR abs/1503.00190 (2015) - [i32]Martin Grohe, Pascal Schweitzer:
Isomorphism Testing for Graphs of Bounded Rank Width. CoRR abs/1505.03737 (2015) - [i31]Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. CoRR abs/1509.08251 (2015) - [i30]Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, Ryan Williams:
Theory and Practice of SAT Solving (Dagstuhl Seminar 15171). Dagstuhl Reports 5(4): 98-122 (2015) - 2014
- [j51]Martin Grohe:
Database Theory Column Report on PODS 2014. SIGACT News 45(4): 83-85 (2014) - [j50]Martin Grohe
, Dániel Marx:
Constraint Solving via Fractional Edge Covers. ACM Trans. Algorithms 11(1): 4:1-4:20 (2014) - [c86]Kristian Kersting, Martin Mladenov, Roman Garnett, Martin Grohe:
Power Iterated Color Refinement. AAAI 2014: 1904-1910 - [c85]André Frochaux, Martin Grohe, Nicole Schweikardt:
Monadic Datalog Containment on Trees. AMW 2014 - [c84]Martin Grohe
:
Algorithmic Meta Theorems for Sparse Graph Classes. CSR 2014: 16-22 - [c83]Martin Grohe
, Kristian Kersting, Martin Mladenov, Erkal Selman:
Dimension Reduction via Colour Refinement. ESA 2014: 505-516 - [c82]Martin Grohe:
Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk). FSTTCS 2014: 31-31 - [c81]Faried Abu Zaid, Erich Grädel, Martin Grohe
, Wied Pakusa:
Choiceless Polynomial Time on Structures with Small Abelian Colour Classes. MFCS (1) 2014: 50-62 - [c80]Martin Grohe
, Stephan Kreutzer, Sebastian Siebertz
:
Deciding first-order properties of nowhere dense graphs. STOC 2014: 89-98 - [e5]Richard Hull, Martin Grohe:
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014. ACM 2014, ISBN 978-1-4503-2375-8 [contents] - [i29]André Frochaux, Martin Grohe, Nicole Schweikardt:
Monadic Datalog Containment on Trees. CoRR abs/1404.0606 (2014) - 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) - [c79]Martin Grohe:
Bounds and Algorithms for Joins via Fractional Edge Covers. In Search of Elegance in the Theory and Practice of Computation 2013: 321-338 - [c78]Christoph Berkholz, Paul S. Bonsma, Martin Grohe
:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. ESA 2013: 145-156 - [c77]Martin Grohe
, Stephan Kreutzer, Sebastian Siebertz
:
Characterisations of Nowhere Dense Graphs (Invited Talk). FSTTCS 2013: 21-40 - [c76]Martin Grohe:
Logical and Structural Approaches to the Graph Isomorphism Problem. MFCS 2013: 42 - [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 - [i28]Martin Grohe, Kristian Kersting, Martin Mladenov, Erkal Selman:
Dimension Reduction via Colour Refinement. CoRR abs/1307.5697 (2013) - [i27]Martin Grohe, Stephan Kreutzer, Sebastian Siebertz:
Deciding first-order properties of nowhere dense graphs. CoRR abs/1311.3899 (2013) - 2012
- [j48]Martin Grohe
, Berit Grußien, André Hernich, Bastian Laubner:
L-Recursion and a new Logic for Logarithmic Space. Log. Methods Comput. Sci. 9(1) (2012) - [j47]Martin Grohe
:
Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM 59(5): 27:1-27:64 (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]Martin Grohe
, Martin Otto:
Pebble Games and Linear Equations. CSL 2012: 289-304 - [c73]Michael Elberfeld, Martin Grohe
, Till Tantau:
Where First-Order and Monadic Second-Order Logic Coincide. LICS 2012: 265-274 - [c72]Martin Grohe:
Structural and logical approaches to the graph isomorphism problem. SODA 2012: 188 - [c71]Martin Grohe
, Dániel Marx:
Structure theorem and isomorphism test for graphs with excluded topological subgraphs. STOC 2012: 173-192 - [i26]Martin Grohe, Martin Otto:
Pebble Games and Linear Equations. CoRR abs/1204.1990 (2012) - [i25]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. Log. Methods Comput. Sci. 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 - [e4]Martin Grohe, Johann A. Makowsky:
Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, Washington, DC, USA, January 5-8, 2009. Contemporary Mathematics 558, American Mathematical Society 2011, ISBN 978-0-8218-4943-9 [contents] - [i24]Martin Grohe, Marc Thurley:
Counting Homomorphisms and Partition Functions. CoRR abs/1104.0185 (2011) - [i23]Martin Grohe, Dániel Marx:
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs. CoRR abs/1111.1109 (2011) - [i22]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]Martin Grohe:
From polynomial time queries to graph structure theory. ICDT 2010: 2 - [c65]Martin Grohe
:
Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors. LICS 2010: 179-188 - [i21]Martin Grohe:
Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs. CoRR abs/1001.2572 (2010) - [i20]Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan:
Finding topological subgraphs is fixed-parameter tractable. CoRR abs/1011.1827 (2010) - [i19]Kord Eickmeyer, Martin Grohe:
Randomisation and Derandomisation in Descriptive Complexity Theory. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j41]Martin Grohe, Götz Schwandtner:
The Complexity of Datalog on Linear Orders. Log. Methods Comput. Sci. 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): 12:1-12:58 (2009) - [j39]Martin Grohe
, Dániel Marx:
On tree width, bramble size, and expansion. J. Comb. Theory 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]Martin Grohe, Stephan Kreutzer:
Methods for Algorithmic Meta Theorems. AMS-ASL Joint Special Session 2009: 181-206 - [c63]Martin Grohe, Marc Thurley:
Counting Homomorphisms and Partition Functions. AMS-ASL Joint Special Session 2009: 243-292 - [c62]Martin Grohe
:
Fixed-Point Definability and Polynomial Time. CSL 2009: 20-23 - [c61]Anuj Dawar
, Martin Grohe, Bjarki Holm, Bastian Laubner:
Logics with Rank Operators. LICS 2009: 113-122 - [c60]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating Homomorphisms. STACS 2009: 231-242 - [c59]Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley:
A Complexity Dichotomy for Partition Functions with Mixed Signs. STACS 2009: 493-504 - [e3]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
The Constraint Satisfaction Problem: Complexity and Approximability, 25.10. - 30.10.2009. Dagstuhl Seminar Proceedings 09441, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [i18]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability 2009 - [i17]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability 2009 - [i16]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) - [c58]Martin Grohe:
Logic, graphs, and algorithms. Logic and Automata 2008: 357-422 - [c57]Kord Eickmeyer
, Martin Grohe
, Magdalena Grüber:
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard. CCC 2008: 8-18 - [c56]Albert Atserias, Martin Grohe
, Dániel Marx:
Size Bounds and Query Plans for Relational Joins. FOCS 2008: 739-748 - [c55]Manuel Bodirsky
, Martin Grohe
:
Non-dichotomies in Constraint Satisfaction Complexity. ICALP (2) 2008: 184-196 - [c54]Martin Grohe
:
The Quest for a Logic Capturing PTIME. LICS 2008: 267-271 - [c53]Martin Grohe
:
Definable Tree Decompositions. LICS 2008: 406-417 - [c52]Isolde Adler, Martin Grohe, Stephan Kreutzer:
Computing excluded minors. SODA 2008: 641-650 - [c51]Martin Grohe
:
Algorithmic Meta Theorems. WG 2008: 30 - [e2]Martin Grohe, Rolf Niedermeier:
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 [contents] - [i15]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. Log. 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): 1:1-1:24 (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) - [c50]Martin Grohe, Martin Hyland, Johann A. Makowsky, Damian Niwinski:
The Ackermann Award 2007. CSL 2007: 589-597 - [c49]Martin Grohe, Magdalena Grüber:
Parameterized Approximability of the Disjoint Cycle Problem. ICALP 2007: 363-374 - [c48]Anuj Dawar
, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt:
Model Theory Makes Formulas Large. ICALP 2007: 913-924 - [c47]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 - [c46]Anuj Dawar
, Martin Grohe
, Stephan Kreutzer:
Locally Excluding a Minor. LICS 2007: 270-279 - [i14]Martin Grohe, André Hernich, Nicole Schweikardt:
Randomized Computations on Large Data Sets: Tight Lower Bounds. CoRR abs/cs/0703081 (2007) - [i13]Yijia Chen, Martin Grohe, Magdalena Grüber:
On Parameterized Approximability. Electron. Colloquium Comput. Complex. TR07 (2007) - [i12]Martin Grohe:
Logic, Graphs, and Algorithms. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [b1]Jörg Flum, Martin Grohe:
Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer 2006, ISBN 978-3-540-29952-3, pp. 1-495 - [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) - [c45]Yijia Chen, Martin Grohe
:
An Isomorphism between Subexponential and Parameterized Complexity Theory. CCC 2006: 314-330 - [c44]Martin Grohe
, Oleg Verbitsky
:
Testing Graph Isomorphism in Parallel by Playing a Game. ICALP (1) 2006: 3-14 - [c43]Yijia Chen, Martin Grohe, Magdalena Grüber:
On Parameterized Approximability. IWPEC 2006: 109-120 - [c42]Anuj Dawar
, Martin Grohe
, Stephan Kreutzer, Nicole Schweikardt:
Approximation Schemes for First-Order Definable Optimisation Problems. LICS 2006: 411-420 - [c41]Martin Grohe:
The Structure of Tractable Constraint Satisfaction Problems. MFCS 2006: 58-72 - [c40]Martin Grohe
, André Hernich, Nicole Schweikardt:
Randomized computations on large data sets: tight lower bounds. PODS 2006: 243-252 - [c39]Martin Grohe, Dániel Marx:
Constraint solving via fractional edge covers. SODA 2006: 289-298 - [e1]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger:
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 [contents] - [i11]Hubie Chen, Martin Grohe:
Constraint Satisfaction with Succinctly Specified Relations. Complexity of Constraints 2006 - [i10]Martin Grohe, Oleg Verbitsky:
Testing Graph Isomorphism in Parallel by Playing a Game. CoRR abs/cs/0603054 (2006) - [i9]Yijia Chen, Martin Grohe:
An Isomorphism between Subexponential and Parameterized Complexity Theory. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j29]Jörg Flum, Martin Grohe
:
Model-checking problems as a basis for parameterized intractability. Log. Methods Comput. Sci. 1(1) (2005) - [j28]Martin Grohe
, Nicole Schweikardt:
The succinctness of first-order logic on linear orders. Log. Methods Comput. Sci. 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) - [c38]Martin Grohe, Christoph Koch, Nicole Schweikardt:
The Complexity of Querying External Memory and Streaming Data. FCT 2005: 1-16 - [c37]Martin Grohe, Christoph Koch, Nicole Schweikardt:
Tight Lower Bounds for Query Processing on Streaming and External Memory Data. ICALP 2005: 1076-1088 - [c36]Albert Atserias, Anuj Dawar
, Martin Grohe:
Preservation Under Extensions on Well-Behaved Finite Structures. ICALP 2005: 1437-1449 - [c35]Martin Grohe, Stephan Kreutzer, Nicole Schweikardt:
The Expressive Power of Two-Variable Least Fixed-Point Logics. MFCS 2005: 422-434 - [c34]Martin Grohe
, Nicole Schweikardt:
Lower bounds for sorting with few random accesses to external memory. PODS 2005: 238-249 - [c33]Georg Gottlob
, Martin Grohe
, Nysret Musliu
, Marko Samer, Francesco Scarcello
:
Hypertree Decompositions: Structure, Algorithms, and Applications. WG 2005: 1-15 - [i8]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger:
05301 Summary - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability 2005 - [i7]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger:
05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability 2005 - [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. Log. 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. Log. 130(1-3): 3-31 (2004) - [j23]Jörg Flum, Martin Grohe:
Parametrized Complexity and Subexponential Time (Column: Computational Complexity). Bull. EATCS 84: 71-100 (2004) - [j22]Martin Grohe
, Nicole Schweikardt:
Comparing the succinctness of monadic query languages over finite trees. RAIRO Theor. Informatics Appl. 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) - [c32]Andrei A. Bulatov, Martin Grohe:
The Complexity of Partition Functions. ICALP 2004: 294-306 - [c31]Jörg Flum, Martin Grohe, Mark Weyer:
Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits. ICALP 2004: 555-567 - [c30]Jörg Flum, Martin Grohe:
Model-Checking Problems as a Basis for Parameterized Intractability. LICS 2004: 388-397 - [c29]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. Comb. 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) - [c28]Yijia Chen, Jörg Flum, Martin Grohe:
Bounded Nondeterminism and Alternation in Parameterized Complexity Theory. CCC 2003: 13-29 - [c27]Martin Grohe, Nicole Schweikardt:
Comparing the Succinctness of Monadic Query Languages over Finite Trees. CSL 2003: 226-240 - [c26]Martin Grohe:
Monadic Datalog on Trees (Invited Talk). FICS 2003: 42-43 - [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]Peter Buneman, Martin Grohe, Christoph Koch:
Path Queries on Compressed XML. VLDB 2003: 141-152 - 2002
- [j15]Martin Grohe
:
Large Finite Structures with Few Lk-Types. Inf. Comput. 179(2): 250-278 (2002) - [j14]Jörg Flum, Markus Frick, Martin Grohe
:
Query evaluation via tree-decompositions. J. ACM 49(6): 716-752 (2002) - [j13]Martin Grohe
:
Parameterized Complexity for the Database Theorist. SIGMOD Rec. 31(4): 86-96 (2002) - [j12]Martin Grohe, Luc Segoufin:
On first-order topological queries. ACM Trans. Comput. Log. 3(3): 336-358 (2002) - [c22]Jörg Flum, Martin Grohe:
The Parameterized Complexity of Counting Problems. FOCS 2002: 538- - [c21]Markus Frick, Martin Grohe
:
The Complexity of First-Order and Monadic Second-Order Logic Revisited. LICS 2002: 215-224 - [c20]Jörg Flum, Martin Grohe:
Describing Parameterized Complexity Classes. STACS 2002: 359-371 - [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]Martin Grohe, Stefan Wöhrle:
An Existential Locality Theorem. CSL 2001: 99-114 - [c17]Jörg Flum, Markus Frick, Martin Grohe:
Query Evaluation via Tree-Decompositions. ICDT 2001: 22-38 - [c16]Martin Grohe:
The Parameterized Complexity of Database Queries. PODS 2001: 82-92 - [c15]Martin Grohe:
Generalized Model-Checking Problems for First-Order Logic. STACS 2001: 12-26 - [c14]Martin Grohe:
Computing crossing numbers in quadratic time. STOC 2001: 231-236 - [c13]Martin Grohe, Thomas Schwentick, Luc Segoufin:
When is the evaluation of conjunctive queries tractable? STOC 2001: 657-666 - 2000
- [j9]Jörg Flum, Martin Grohe:
On Fixed-Point Logic With Counting. J. Symb. Log. 65(2): 777-787 (2000) - [j8]Martin Grohe, Thomas Schwentick:
Locality of order-invariant first-order formulas. ACM Trans. Comput. Log. 1(1): 112-130 (2000) - [c12]Martin Grohe, Luc Segoufin:
On First-Order Topological Queries. LICS 2000: 349-360 - [c11]Michael Benedikt, Martin Grohe, Leonid Libkin, Luc Segoufin:
Reachability and Connectivity Queries in Constraint Databases. PODS 2000: 104-115 - [c10]Martin Grohe:
Isomorphism testing for embeddable graphs through definability. STOC 2000: 63-72 - [i3]Markus Frick, Martin Grohe:
Deciding first-order properties of locally tree-decomposable structures. CoRR cs.DS/0004007 (2000) - [i2]Martin Grohe:
Computing Crossing Numbers in Quadratic Time. CoRR cs.DS/0009010 (2000)
1990 – 1999
- 1999
- [j7]Martin Grohe:
Equivalence in Finite-Variable Logics is Complete for Polynomial Time. Comb. 19(4): 507-532 (1999) - [c9]Martin Grohe:
Descriptive and Parameterized Complexity. CSL 1999: 14-31 - [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. Bull. Symb. Log. 4(4): 345-398 (1998) - [c6]Martin Grohe:
Fixed-Point Logics on Planar Graphs. LICS 1998: 6-15 - [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]Martin Grohe
:
Canonization for Lk-equivalence is Hard. CSL 1997: 220-238 - [c3]Martin Grohe:
Large Finite Structures with Few Lk-Types. LICS 1997: 216-227 - 1996
- [j4]Martin Grohe, Lauri Hella
:
A double arity hierarchy theorem for transitive closure logic. Arch. Math. Log. 35(3): 157-171 (1996) - [j3]Martin Grohe
:
Arity Hierarchies. Ann. Pure Appl. Log. 82(2): 103-163 (1996) - [j2]Martin Grohe:
Some Remarks on Finite Löwenheim-Skolem Theorems. Math. Log. Q. 42: 569-571 (1996) - [c2]Martin Grohe:
Equivalence in Finite-Variable Logics is Complete for Polynomial Time. FOCS 1996: 264-273 - 1995
- [j1]Martin Grohe:
Complete Problems for Fixed-Point Logics. J. Symb. Log. 60(2): 517-527 (1995) - 1993
- [c1]Martin Grohe:
Bounded-Arity Hierarchies in Fixed-Point Logics. CSL 1993: 150-164
Coauthor Index
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 01:25 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint