Person
Prof. Dr. rer. nat.Martin Grohe
UniversitätsprofessorAddress
Building: E1, 1. Etage
Room: 4116a
Ahornstraße 55
52074 Aachen
Contact
- WorkPhone
- Phone: +49 241 80 21700
Office Hour
Tuesdays, 2:00 - 3:00 pm
It's usually a good idea to write me an email before you come, because sometimes I'm away (e.g. at a conference). However, during the semster I'm usually in my office for the office hour, so feel free to come unannonced. If you prefer to talk via zoom, that's also possible. In this case, please send me an email.
Research Interests
Algorithms und complexity, logic, database theory, graph theory, machine learning
Books
| Title | Author(s) | Published |
|---|---|---|
|
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
|
Martin Grohe |
Lecture Notes in Logic, Volume 47. Cambridge University Press, 2017 |
| Model Theoretic Methods in Finite Combinatorics | Martin Grohe, Janos Makowsky (Ed.) | Contemporary Mathematics 558, American Mathematical Society, 2011 |
| Martin Grohe, Jörg Flum |
Springer-Verlag, 2006 |
Publications
| Title | Author(s) | Published in |
|---|---|---|
| One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction | Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe |
Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023 |
| Some Might Say All You Need Is Sum | Eran Rosenbluth and Jan Tönshoff and Martin Grohe |
Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023 |
| WL meets VC | Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe |
Proceedings of the International Conference on Machine Learning, 2023 |
| The Descriptive Complexity of Graph Neural Networks | Martin Grohe |
Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023 |
| The Iteration Number of the Weisfeiler-Leman Algorithm | Martin Grohe, Moritz Lichter, and Daniel Neuen |
Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023 |
| Simulating Logspace-Recursion with Logarithmic Quantifier Depth | Steffen van Bergerem, Martin Grohe, Sandra Kiefer, and Luca Oeljeklaus |
Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023 |
| Solving AC Power Flow with Graph Neural Networks under Realistic Constraints | Luis Böttcher, Hinrikus Wolf, Bastian Jung, Philipp Lutat, Marc Trageser, Oliver Pohl, Xiaohu Taoi, Andreas Ulbig, and Martin Grohe |
Proceedings of IEEE Belgrade PowerTech, 2023 |
| Stable Tuple Embeddings for Dynamic Databases | Jan Tönshoff and Neta Friedman and Martin Grohe and Benny Kimelfeld |
Proceedings of the 39th IEEE International Conference on Data Engineering, 2023 |
| Probabilistic Query Evaluation with Bag Semantics | Martin Grohe, Peter Lindner, and Christoph Standke |
Proceedings of the 26th International Conference on Database Theory, 2023. |
| Isomorphism Testing for Graphs Excluding Small Minors | Martin Grohe, Daniel Neuen, and Daniel Wiebking |
SIAM Journal on Computing 52(1), 2023. Conference version in Proceedings of the 61st IEEE Symposium on Foundations of Computer Science, 2020. |
| Graph Machine Learning for Design of High-Octane Fuels | Jan G. Rittig, Martin Ritzert, Artur M. Schweidtmann, Stefanie Winkler, Jana M. Weber, Philipp Morsch, K. Alexander Heufer, Martin Grohe, Alexander Mitsos, and Manuel Dahmen |
AIChe Journal 69(4), 2023. |
| Physical Pooling Functions in Graph Neural Networks for Molecular Property Prediction | Artur M. Schweidtmann, Jan G. Rittig, Jana M. Weber, Martin Grohe. Manuel Dahmen, Kai Leonhard, and Alexander Mitsos |
Computers and Chemical Engineering 172, 2023. |
| Canonisation and Definability for Graphs of Bounded Rank Width | Martin Grohe and Daniel Neuen |
ACM Transaction on Computational Logic 24(1), 2023. Conference version in Proceedings of the 34th ACM-IEEE Symposium on Logic in Computer Science, 2019. |
| Classification of material properties and their relation to chemical bonding: Essential steps towards the inverse design of materials with tailored functionalities | Carl-Friedrich Schön, Steffen van Bergerem, Christian Mattes, Aakash Yadav, Martin Grohe, Leif Kobbelt und Matthias Wuttig | Science Advances 47(8), 2022. |
| Generative Datalog with Continuous Distributions | Martin Grohe, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Peter Lindner |
Journal of the ACM 69(6), 2002. Conference Version in Proceedings of the 39th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2020. |
| Independence in Probabilistic Databases | Martin Grohe and Peter Lindner |
Journal of the ACM 69(5), 2022. |
| Graph Similarity Based on Matrix Norms | Timo Gervens and Martin Grohe |
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022. |
| Homomorphism Tensors and Linear Equations | Martin Grohe, Gaurav Rattan, and Tim Seppelt |
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022 |
| On the Parameterized Complexity of Learning First-Order Logic |
Steffen van Bergerem, Martin Grohe, and Martin Ritzert |
Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2022 |
| Infinite Probabilistic Databases | Martin Grohe and Peter Lindner |
Logical Methods in Computer Science 18(1), 2022 Conference version in Proceedings of the 23rd International Conference on Database Theory, 2020 |
| The Logic of Graph Neural Networks | Martin Grohe |
Proceedings of the 35th ACM-IEEE Symposium on Logic in Computer Science, 2020 |
| The Effects of Randomness on the Stability of Node Embeddings | Tobias Schumacher and Hinrikus Wolf and Martin Ritzert and Florian Lemmerich and Jan Bachmann and Florian Frantzen and Max Klabunde and Martin Grohe and Markus Strohmaier |
Machine Learning and Principles and Practice of Knowledge Discovery in Databases - International Workshops of ECML PKDD 2021, Proceedings, Part I |
| Logarithmic Weisfeiler-Leman Identifies All Planar Graphs | Martin Grohe and Sandra Kiefer |
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021 |
| Isomorphism, Canonisation, and Definability for Graphs of Bounded Rank Width | Martin Grohe and Daniel Neuen |
Communications of the ACM 64(5), 2021. |
| Probabilistic Data with Continuous Distributions | Martin Grohe, Benjamin Lucien Kaminski, Joost-Pieter Katoen, Peter Lindner |
SIGMOD Record, Vol 50, No1, 2021. |
| Recent Advances on the Graph Isomorphism Problem | Martin Grohe and Daniel Neuen |
In Surveys in Combinatorics, LMS Lecture Note Series, Cambridge University Press, 2021. |
| The Surprising Power of Graph Neural Networks with Random Node Initialization | Ralph Abboud, İsmail İlkan Ceylan, Martin Grohe, Thomas Lukasiewicz |
Proceedings of the 30th International Joint Conference on Artificial Intelligence, 2021. |
| Tuple-Independent Representations of Infinite Probabilistic Databases | Nofar Carmeli, Martin Grohe, Peter Lindner, Christoph Standke |
Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021. |
| Database Repairing with Soft Functional Dependencies | Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, Muhammad Tibi |
Proceedings of the 24th International Conference on Database Theory, 2021. |
| Definable decompositions for graphs of bounded linear clique width | Mikołaj Bojańczyk, Martin Grohe and Michał Pilipczuk |
Logical Methods in Computer Science 17(1), 2021. Conference version in Proceedings of the 33rd ACM-IEEE Symposium on Logic in Computer Science, 2018 |
| Graph Neural Networks for Maximum Constraint Satisfaction | Jan M. Tönshoff, Martin Ritzert, Hinrikus Wolf, Martin Grohe |
Frontiers in Artificial Intelligence 3, 2021. |
| Deep Weisfeiler Leman | Martin Grohe, Pascal Schweitzer, Daniel Wiebking |
Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, 2021. |
| Color Refinement and its Applications | Martin Grohe, Kristian Kersting, Martin Mladenov, Pascal Schweitzer |
In Guy Van den Broeck, Kristian Kersting, Sriraam Natarajan, David Poole, An Introduction to Lifted Probabilistic Inference, MIT Press, 2021. |
| The Graph Isomorphism Problem | Martin Grohe, Pascal Schweitzer |
Communications of the ACM 63(11):128-134, 2020 |
| Graph Neural Networks for Prediction of Fuel Ignition Quality | Artur M. Schweidtmann, Jan G. Rittig, Andrea König, Martin Grohe, Alexander Mitsos, and Manuel Dahmen |
Energy and Fuels 34(9):11395-11407, 2020. |
|
Martin Grohe, Daniel Neuen, Pascal Schweitzer, Daniel Wiebking |
ACM Transactions on Algorithms 16(3), 2020. Conference version in: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018. |
|
| Counting Bounded Tree Depth Homomorphisms | Martin Grohe |
Proceedings of the 35th ACM-IEEE Symposium on Logic in Computer Science, 2020. |
| word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data | Martin Grohe |
Proceedings of the 39th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2020. |
| A Finite-Model-Theoretic View on Propositional Proof Complexity | Erich Grädel, Martin Grohe, Benedikt Pago and Wied Pakusa | Logical Methods in Computer Science 15(1), 2019. |
| A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus | Martin Grohe, Sandra Kiefer |
Proceedings of the 46th International Colloquium on Automata, Languages and Programming, 2019. |
| The Complexity of Homomorphism Indistinguishability | Jan Böker, Yijia Chen, Martin Grohe, Gaurav Rattan |
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019. |
|
Weisfeiler and Leman go neural: Higher-order graph neural networks |
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe |
Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019. |
|
Probabilistic databases with an infinite open-world assumption |
Martin Grohe, Peter Lindner |
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2019. |
|
Colouring and Covering Nowhere Dense Graphs
|
Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos Stavrpoulos |
SIAM Journal on Discrete Mathematics 32(4):2467-2481, 2018. Conference version in: Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science, 2015. |
| Martin Grohe, Daniel Neuen, Pascal Schweitzer |
In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, pages 89–100, 2018. |
|
| Martin Grohe, Gaurav Rattan, Gerhard Woeginger |
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018 |
|
| Holger Dell, Martin Grohe, Gaurav Rattan |
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018 |
|
| First-Order Query Evaluation with Cardinality Conditions | Martin Grohe, Nicole Schweikardt |
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2018. |
| Learning MSO-Definable Hypotheses on Strings | Martin Grohe, Christof Löding, Martin Ritzert |
Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017. |
|
Yijia Chen, Martin Grohe, BingKai Lin |
Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, 2017. |
|
|
Learning first-order definable concepts over structures of small degree |
Martin Grohe, Martin Ritzert |
Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017. |
| Descriptive Complexity of Solving Linear Equation Systems and its Applications |
Martin Grohe, Wied Pakusa |
Proceedings of the 32nd IEEE Symposium on Logic in Computer Science, 2017. |
| Deciding First-Order properties of Nowhere Dense Graphs | Martin Grohe, Stephan Kreutzer, Sebastian Siebertz |
Journal of the ACM 64(3), 2017. Conference version in: Proceedings of the 46th ACM Symposium on Theory of Computing, 2014 |
|
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement |
Christoph Berkholz, Paul Bonsma, Martin Grohe |
Theory of Computing Systems 60(4):581-614, 2017 Conference version in: Proceedings of the 21st Annual European Symposium on Algorithms, 2013. |
| Linear Diophantine Equations, Group CSPs, and Graph Isomorphism | Christoph Berkholz, Martin Grohe |
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.327-339, 2017. |
| Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles) | Martin Grohe | arXiv:1605.06704 |
| Quasi-4-Connected Components | Martin Grohe |
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
| Michael Elberfeld, Marlin Frickenschmidt, Martin Grohe |
Proceedings of the 31st IEEE Symposium on Logic in Computer Science (LICS 2016), pp.397-406, 2016 |
|
| Martin Grohe, Pascal Schweitzer |
SIAM Journal on Discrete Mathematics, 30(2):1213-1247, 2016 Conference version in: Proceedings of the 47th ACM Symposium on Theory of Computing (STOC'15), pp.683-692, 2015 |
|
| Where First-Order and Monadic Second-Order Logic Coincide | Michael Elberfeld, Martin Grohe, Till Tantau |
ACM Transactions on Computational Logic, 17(4):25:1-25:18, 2016 Conference version in: Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LICS 2012, pp.265-274, 2012 |
| Martin Grohe |
Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA 2016). Lecture Notes in Computer Science 9618, pp.24-42, 2016 |
|
| Isomorphism Testing for Graphs of Bounded Rank Width | Martin Grohe, Pascal Schweitzer |
Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS15), pp.1010-1029, 2015 |
| Erich Grädel, Martin Grohe |
Fields of Logic and Computation II - Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday. Lecture Notes in Computer Science 9300, pp.193-209, 2015 |
|
|
Limitations of Algebraic Approaches to Graph Isomorphism Testing |
Christoph Berkholz, Martin Grohe |
Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015), Part II. Lecture Notes in Computer Science 9134, pp.155-166, 2015 |
| Martin Grohe |
Encyclopedia of Applied and Computational Mathematics, Springer Verlag, 2015 |
|
| Pebble Games and Linear Equations | Martin Grohe, Martin Otto |
Journal of Symbolic Logic 80(3), 2015 Conference version in: Proceedings of the 26th International Workshop on Computer Science Logic (CSL'12), Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, 2012 |
|
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs |
Martin Grohe, Dániel Marx |
SIAM Journal on Computing 44(1):114-159, 2015 Conference version in: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC'12), pp.173-192, 2012 |
| Constraint Solving via Fractional Edge Covers | Martin Grohe, Dániel Marx |
ACM Transactions on Algorithms 11(1), 2014 Conference version in: Proceedings of the of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp.289-298, 2006 |
|
Choiceless Polynomial Time on Structures with Small Abelian Colour Classes |
Faried Abu Zaid, Erich Grädel, Martin Grohe, Wied Pakusa |
Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), Part I. Lecture Notes in Computer Science 8634, pp.50-62, 2014 |
| Martin Grohe, Kristian Kersting, Martin Mladenov, Erkal Selman |
Proceedings of the 22nd Annual European Symposium on Algorithms. Lecture Notes in Computer Science 8737, pp. 505–516, 2014 |
|
| Power Iterated Color Refinement | Kristian Kersting, Martin Mladenov, Roman Garnett, Martin Grohe | Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI'14), pp. 1904–1910, 2014 |
| Martin Grohe |
Proceedings of the 9th International Computer Science Symposium in Russia (CSR'14). Lecture Notes in Computer Science 8476, pp.16-22, 2014 |
|
|
Monadic Datalog Containment on Trees
|
André Frochaux, Martin Grohe, Nicole Schweikardt |
Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management (AMW 2014) |
| Size bounds and query plans for relational joins | Martin Grohe, Albert Atserias and Dániel Marx |
SIAM Journal on Computing 42(4):1737-1767, 2013 Conference version in: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739-748, 2008 |
| Martin Grohe, Stephan Kreutzer, Sebastian Siebertz |
Proceedings of the 32nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) |
|
| Martin Grohe |
In Search of Elegance in the Theory and Practice of Computation, Essays Dedicated to Peter Buneman. Lecture Notes in Computer Science 8000, pp.321-338, 2013. |
|
| A Simple Algorithm for the Graph Minor Decomposition — Logic Meets Structural Graph Theory — | Martin Grohe, Ken-ichi Kawarabayashi, Bruce Reed |
Proceedings of the of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp.414-431, 2013 |
| Fixed-Point Definability and Polynomial Time on Graph with Excluded Minors | Martin Grohe |
Journal of the ACM 59(5), 2012 Conference version in Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LICS'10), 2010 |
| Enumerating Homomorphisms | Martin Grohe, Andrei A. Bulatov, Victor Dalmau, Dániel Marx |
Journal of Computer and System Sciences 78:638-650, 2012 Conference version in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.231-242, 2009 |
| L-Recursion and a new Logic for Logarithmic Space | Martin Grohe, Berit Grußien, André Hernich, Bastian Laubner |
Logical Methods in Computer Science 9(1), 2012 Conference version in Proceedings of the 25th International Workshop on Computer Science Logic (CSL'11) |
| Methods for Algorithmic Meta Theorems | Martin Grohe, Stephan Kreutzer |
Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011 |
| Counting Homomorphisms and Partition Functions | Martin Grohe, Marc Thurley |
Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, American Mathematical Society, 2011 |
| From Polynomial Time Queries to Graph Structure Theory | Martin Grohe | Communications of the ACM 54(6):104-112, 2011 |
| Finding Topological Subgraphs is Fixed-Parameter Tractable | Martin Grohe, Dániel Marx, Ken-Ich Kawarbayashi, Paul Wollan |
Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pp.479-488, 2011 |
| Randomisation and Derandomisation in Descriptive Complexity Theory |
Martin Grohe, Kord Eickmeyer |
Logical Methods in Computer Science, Volume 7, Issue 3, 2011 Conference version in Proceedings of the 24th International Workshop on Computer Science Logic (CSL'10), pp.275-289, 2010 |
|
Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs |
Martin Grohe |
Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday |
| A complexity dichotomy for partition functions with mixed signs | Martin Grohe, Leslie Ann Goldberg, Mark Jerrum, Marc Thurley |
SIAM Journal on Computing 39:336-402, 2010 Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.493-504, 2009 |
| Constraint satisfaction problems with succinctly specified relations | Martin Grohe, Hubie Chen | Journal of Computer and System Sciences 76(8):847-860, 2010 |
| Martin Grohe | Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), pp.20-23, 2009 | |
| Logics with Rank Operators | Martin Grohe, Anuj Dawar, Bjarki Holm, Bastian Laubner | Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS'09), pp.113-122, 2009 |
| Lower bounds for processing data with few random accesses to external memory | Martin Grohe, Andre Hernich, Nicole Schweikardt |
Journal of the ACM, 56(3), 2009 Full version of PODS'05 and PODS'06 papers |
| Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, Jan Van den Bussche |
Theory of Computing Systems, 44:533-560, 2009 Proceedings of the 11th International Conference on Database Theory (ICDT'07) |
|
| The Complexity of Datalog on Linear Orders | Martin Grohe, Götz Schwandtner | Logical Methods in Computer Science, 5(1), 2009 |
| On tree width, bramble size, and expansion | Martin Grohe, Dániel Marx | Journal of Combinatorial Theory, Series B 99:218-228, 2009 |
|
Preservation under Extensions on Well-Behaved Finite Structures |
Martin Grohe, Albert Atserias, Anuj Dawar |
SIAM Journal on Computing, 38:1364-1381, 2008 Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05) |
| Martin Grohe, Manuel Bodirsky |
Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08, Track B) |
|
| Definable tree decompositions | Martin Grohe | Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.406-417, 2008 |
| The quest for a logic capturing PTIME | Martin Grohe | Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.267-271, 2008 |
| Approximation of natural W[P]-complete minimisation problems is hard | Martin Grohe, Kord Eickmeyer, Magdalena Grüber | Proceedings of the 23rd IEEE Conference on Computational Complexity (CCC'08), pp.8-18, 2008 |
| Computing excluded minors | Martin grohe, Isolde Adler, Stephan Kreutzer | Proceedings of the of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp.641-650, 2008 |
| Logic, graphs, and algorithms | Martin Grohe, | Logic and Automata – History and Perspectives, Amsterdam University Press, 2007 |
| An Isomorphism between Subexponential and Parameterized Complexity Theory | Martin Grohe, Yijia Chen |
SIAM Journal on Computing 37:1228-1258, 2007 Proceedings of the 21st IEEE Conference on Computational Complexity (CCC'06), pp.314-328, 2006 |
| Bounded Fixed-Parameter Tractability and Reducibility | Martin Grohe, Rod Downey, Jörg Flum, Mark Weyer | Annals of Pure and Applied Logic 148:1-19, 2007 |
| Martin Grohe, Magdalena Grüber |
Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A) |
|
| Martin Grohe, Anuj Dawar, Stephan Kreutzer, Nicole Schweikardt |
Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track B) |
|
| Locally Excluding a Minor | Martin Grohe, Anuj Dawar, Stephan Kreutzer | Proceedings of the 21st IEEE Symposium on Logic in Computer Science (LICS'07), pp.270-279, 2007 |
|
The complexity of homomorphism and constraint satisfaction problems seen from the other side |
Martin Grohe |
Journal of the ACM, 54(1), 2007 Proceedings of the 44th IEEE Symposium on Foundations of Comupter Science (FOCS'03), pp.552-561, 2003 |
| Martin Grohe, Isolde Adler and Georg Gottlob |
European Journal of Combinatorics, 28:2167-2181, 2007 Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05) DMTCS Proceedings Series, Volume AE, pp.5-10, 2005 |
|
|
Tight Lower Bounds for Query Processing on Streaming and External Memory Data External Memory |
Martin Grohe, Christoph Koch, Nicole Schweikardt |
Theoretical Computer Science 380:199-217, 2007 Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05) |
| An analysis of the W*-hierarchy | Martin Grohe, Yijia Chen, Jörg Flum | Journal of Symbolic Logic 72:513-534, 2007 |
| Martin Grohe, Yijia Chen, Magdalena Grüber |
Proceedings of the 2nd International Workshop on Parameterized and Exact Computation |
|
| Approximation Schemes for First-Order Definable Optimisation Problems | Martin Grohe, Anuj Dawar, Stephan Kreutzer, Nicole Schweikardt | Proceedings of the 21st IEEE Symposium on Logic in Computer Science, pp.411-420, 2006 |
| Martin Grohe |
roceedings of the 31st Symposium on Mathematical Foundations of Computer Science |
|
| Martin Grohe, Oleg Verbitzky |
Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Part I |
|
| Randomized Computations on Large Data Sets: Tight Lower Bounds | Martin Grohe, Andre Hernich, Nicole Schweikardt | Proceedings of the 25th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'06), pp.243-252, 2006 |
|
Bounded fixed-parameter tractability and log2n nondeterministic bits |
Martin Grohe, örg Flum, Mark Weyer |
Journal of Computer and System Sciences 72:34-71, 2006 Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04) |
| Martin Grohe, Andrei Bulatov |
Theoretical Computer Science 348:148-186, 2005 Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04) |
|
|
Hypertree Decompositions: Structure, Algorithms, and Applications |
Martin Grohe, Georg Gottlob, Nysret Musliu, Marko Samer, Francesco Scarcello |
Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05) |
|
The expressive power of two-variable least fixed-point logics |
Martin Grohe, Stephan Kreutzer, Nicole Schweikardt |
Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS'05) |
| The succinctness of first-order logic on linear orders | Martin Grohe, Nicole Schweikardt |
Logical Methods in Computer Science, 1(1), 2005 Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp. 438-447, 2004 |
|
Martin Grohe, Yijia Chen, Jörg Flum |
Theoretical Computer Science., 339:167-199, 2005 | |
|
The complexity of querying external memory and streaming data |
Martin Grohe, Christoph Koch, Nicole Schweikardt |
Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT'05) |
|
Lower Bounds for Sorting with Few Random Accesses to External Memory |
Martin Grohe, Nicole Schweikardt | Proceedings of the 24th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'05), pp.238-249, 2005 |
| Model-Checking Problems as a Basis for Parameterized Intractability | Martin Grohe, Jörg Flum |
Logical Methods in Computer Science 1(1), 2005 Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp.388-397, 2004 |
|
The complexity of first-order and monadic second-order logic revisited |
Martin Grohe, Markus Frick |
Annals of Pure and Applied Logic 130: 3-31, 2004 Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02), pp. 215-224, 2002 |
| Parameterized Complexity and Subexponential Time | Martin Grohe, Jörg Flum | Bulletin of the European Association for Theoretical Computer Science 84, October 2004 |
| Martin Grohe, Jörg Flum |
SIAM Journal on Computing 33:892-922, 2004 Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02), pp. 538-547, 2002 |
|
| Martin Grohe, Stefan Wöhrle |
Annals of Pure and Applied Logic, 129: 131-148, 2004 Proceedings of the 10th Annual Conference of the European Association for Computer Science Logic (CSL'01) Lecture Notes in Computer Science 2142, pp.99-114, Springer-Verlag 2001 |
|
| Martin Grohe |
Journal of Computer and System Sciences, 68(2):285-302, 2004 Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.231-236, 2001 |
|
|
Learnability and Definability in Trees and Similar Structures |
Martin Grohe, Gyorgy Turan |
Theory of Computing Systems 37(1):193-220, 2004 Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS'02) Lecture Notes in Computer Science 2285, pp.645-658, Springer-Verlag 2002 |
|
Local tree-width, excluded minors, and approximation algorithms |
Martin Grohe | Combinatorica 23(4):613-632, 2003 |
| Martin Grohe, Jörg Flum |
Information and Computation 187: 291-319, 2003 Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS'02) Lecture Notes in Computer Science 2285, pp.359-371, Springer-Verlag 2002 |
|
|
Comparing the succinctness of monadic query languages over finite trees |
Martin Grohe, Nicole Schweikardt |
RAIRO - Theoretical Informatics and Applications (ITA) 38:343-373, 2004 Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03) |
| Path Queries on Compressed XML | Martin Grohe, Peter Buneman, Christoph Koch | Proceedings of the 29th Conference on Very Large Data Bases (VLDB 2003), pp.141-152, 2003 |
| Query Evaluation on Compressed Trees | Martin Grohe, Markus Frick, Christoph Koch | Conference version in Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS'03), pp.188-197, 2003 |
|
Bounded Nondeterminism and Alternation in Parameterized Complexity Theory |
Martin Grohe, Yijia Chen, Jörg Flum | Proceedings of the 18th IEEE Conference on Computational Complexity (CCC'03), pp.13-29, 2003 |
|
Reachability and Connectivity Queries in Constraint Databases |
Martin Grohe, Michael Benedikt, Leonid Libkin, Luc Segoufin |
Journal of Computer System Sciences 66(1):169-206, 2003 roceedings of the 19th ACM Symposium on Principles of Database Systems (PODS'00), 2000 |
| Parameterized Complexity for the Database Theorist | Martin Grohe | SIGMOD Record 31(4), 2002 |
| Martin Grohe, Jörg Flum, Markus Frick |
Journal of the ACM 49:716-752, 2002 Proceedings of the 8th International Conference on Database Theory Lecture Notes in Computer Science 1973, Springer-Verlag, 2001 |
|
| Martin Grohe, Luc Segoufin |
ACM Transactions on Computational Logic 3(3):336-358, 2002 Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000 |
|
| Martin Grohe |
Information and Computation 179(2): 250-278, 2002 Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, 1997 |
|
| Martin Grohe, Thomas Schwentick, Luc Segoufin | Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.657-666, 2001 | |
| Martin Grohe | Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'01), pp.82-92, 2001 | |
|
Fixed-parameter tractability, definability, and model checking |
Martin Grohe, Jörg Flum | SIAM Journal on Computing 31:113-145, 2001 |
| Martin Grohe |
Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01) Lecture Notes in Computer Science 2010, pp.12-26, Springer-Verlag 2001 |
|
|
Deciding first-order properties of locally tree-decomposable structures |
Martin Grohe, Markus Frick |
Journal of the ACM 48:1184-1206, 2001 Proceedings of the 26th International Colloquium on Automata, Languages, and Programming Lecture Notes in Computer Science 1644, Springer-Verlag, 1999 |
|
Isomorphism testing for embeddable graphs through definability |
Martin Grohe | Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000 |
| Martin Grohe, Thomas Schwentick |
ACM Transactions on Computational Logic 1:112-130, 2000 Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science Lecture Notes in Computer Science 1450, Springer-Verlag, 1998 |
|
| On fixed-point logic with counting | Martin Grohe, Jörg Flum |
Journal of Symbolic Logic 65:777- 787, 2000 |
| Equivalence in finite-variable logics is complete for polynomial time | Martin Grohe | Combinatorica 19:507-532, 1999 |
| Martin Grohe |
Computer Science Logic, 13th Workshop (CSL'99) Lecture Notes in Computer Science 1683, Springer-Verlag, 1999 |
|
|
Definability and descriptive complexity on databases of bounded tree-width |
Martin Grohe, Julian Marino |
Proceedings of the 7th International Conference on Database Theory (ICDT'99) Lecture Notes in Computer Science 1540, Springer-Verlag, 1999 |
| Zur Struktur dessen, was wirklich berechenbar ist | Martin Grohe, Heinz-Dieter Ebbinghaus | Philosophia Naturalis 36:91-116, 1999 |
| Finite variable logics in descriptive complexity theory | Martin Grohe |
Bulletin of Symbolic Logic 4:345-398, 1998 |
| Martin Grohe | Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS'98), 1998 | |
| Martin Grohe |
Computer Science Logic (CSL'97), 11th Workshop, 1997 Lecture Notes in Computer Science 1414, Springer Verlag 1998 |
|
| Martin Grohe | Journal of Logic and Computation 7: 205-228, 1997 | |
| Martin Grohe | Annals of Pure and Applied Logic 82: 103-163, 1996 | |
| Martin Grohe | Mathematical Logic Quarterly 42: 569-571, 1996 | |
|
A double arity hierarchy theorem for transitive closure logic |
Martin Grohe, Lauri Hella | Archive for Mathematical Logic 35:157-171, 1996 |
| Martin Grohe | Journal of Symbolic Logic 60: 517-527, 1995 | |
| Martin Grohe |
Computer Science Logic (CSL'93), 7th Workshop, Swansea 1993 |
|
| The Complexity of Finite-Variable Theories | Martin Grohe | Habilitationsschrift at the Albert-Ludwigs-Universität Freiburg, November 1997 |
| The Structure of Fixed-Point Logics | Martin Grohe | Dissertation at the Albert-Ludwigs-Universität Freiburg, December 1994 |
| Fixpunktlogiken in der endlichen Modelltheorie | Martin Grohe | Diplomarbeit at the Albert-Ludwigs-Universität Freiburg, April 1992 |