Grohe, Martin; Neuen, Daniel; Schweitzer, Pascal A faster isomorphism test for graphs of small degree. (English) Zbl 07780701 SIAM J. Comput. 52, No. 6, FOCS18-1-FOCS18-36 (2023). MSC: 68Q25 68R10 68W05 20B40 20B15 PDFBibTeX XMLCite \textit{M. Grohe} et al., SIAM J. Comput. 52, No. 6, FOCS18--1-FOCS18--36 (2023; Zbl 07780701) Full Text: DOI arXiv
Grohe, Martin; Neuen, Daniel; Wiebking, Daniel Isomorphism testing for graphs excluding small minors. (English) Zbl 1511.68203 SIAM J. Comput. 52, No. 1, 238-272 (2023). Reviewer: I. M. Erusalimskiy (Rostow-na-Donu) MSC: 68R10 05C25 05C60 05C83 05C85 20B25 68Q25 PDFBibTeX XMLCite \textit{M. Grohe} et al., SIAM J. Comput. 52, No. 1, 238--272 (2023; Zbl 1511.68203) Full Text: DOI arXiv
Grohe, Martin; Neuen, Daniel Canonisation and definability for graphs of bounded rank width. (English) Zbl 07650602 ACM Trans. Comput. Log. 24, No. 1, Paper No. 6, 31 p. (2023). MSC: 03B70 68-XX PDFBibTeX XMLCite \textit{M. Grohe} and \textit{D. Neuen}, ACM Trans. Comput. Log. 24, No. 1, Paper No. 6, 31 p. (2023; Zbl 07650602) Full Text: DOI arXiv
van Bergerem, Steffen; Grohe, Martin; Kiefer, Sandra; Oeljeklaus, Luca Simulating Logspace-Recursion with Logarithmic Quantifier Depth. arXiv:2304.12948 Preprint, arXiv:2304.12948 [cs.LO] (2023). BibTeX Cite \textit{S. van Bergerem} et al., ``Simulating Logspace-Recursion with Logarithmic Quantifier Depth'', Preprint, arXiv:2304.12948 [cs.LO] (2023) Full Text: arXiv OA License
Grohe, Martin; Lindner, Peter Independence in infinite probabilistic databases. (English) Zbl 07679905 J. ACM 69, No. 5, Paper No. 37, 42 p. (2022). MSC: 68-XX PDFBibTeX XMLCite \textit{M. Grohe} and \textit{P. Lindner}, J. ACM 69, No. 5, Paper No. 37, 42 p. (2022; Zbl 07679905) Full Text: DOI arXiv
Grohe, Martin; Lindner, Peter Infinite probabilistic databases. (English) Zbl 07566047 Log. Methods Comput. Sci. 18, No. 1, Paper No. 34, 43 p. (2022). MSC: 03B70 68-XX PDFBibTeX XMLCite \textit{M. Grohe} and \textit{P. Lindner}, Log. Methods Comput. Sci. 18, No. 1, Paper No. 34, 43 p. (2022; Zbl 07566047) Full Text: arXiv Link
Gervens, Timo; Grohe, Martin Graph Similarity Based on Matrix Norms. arXiv:2207.00090 Preprint, arXiv:2207.00090 [cs.DM] (2022). BibTeX Cite \textit{T. Gervens} and \textit{M. Grohe}, ``Graph Similarity Based on Matrix Norms'', Preprint, arXiv:2207.00090 [cs.DM] (2022) Full Text: arXiv OA License
Grohe, Martin; Schweitzer, Pascal; Wiebking, Daniel Deep Weisfeiler Leman. (English) Zbl 07788492 Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2600-2614 (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{M. Grohe} et al., in: Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2600--2614 (2021; Zbl 07788492) Full Text: DOI arXiv
Grohe, Martin A deep dive into the Weisfeiler-Leman algorithm (Invited Talk). (English) Zbl 07724175 Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 2, 1 p. (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{M. Grohe}, LIPIcs -- Leibniz Int. Proc. Inform. 202, Article 2, 1 p. (2021; Zbl 07724175) Full Text: DOI
Grohe, Martin; Neuen, Daniel Recent advances on the graph isomorphism problem. (English) Zbl 1504.05193 Dabrowski, Konrad K. (ed.) et al., Surveys in combinatorics 2021. Based on plenary lectures given at the 28th British combinatorial conference, hosted online by Durham University, Durham, UK, July 5–9, 2021. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 470, 187-234 (2021). MSC: 05C60 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{D. Neuen}, Lond. Math. Soc. Lect. Note Ser. 470, 187--234 (2021; Zbl 1504.05193) Full Text: arXiv Link
Schmitt-Grohé, Stephanie; Uribe, Martín Multiple equilibria in open economies with collateral constraints. (English) Zbl 1481.91112 Rev. Econ. Stud. 88, No. 2, 969-1001 (2021). MSC: 91B52 91G45 PDFBibTeX XMLCite \textit{S. Schmitt-Grohé} and \textit{M. Uribe}, Rev. Econ. Stud. 88, No. 2, 969--1001 (2021; Zbl 1481.91112) Full Text: DOI
Bojańczyk, Mikołaj; Grohe, Martin; Pilipczuk, Michał Definable decompositions for graphs of bounded linear cliquewidth. (English) Zbl 1509.03119 Log. Methods Comput. Sci. 17, No. 1, Paper No. 5, 40 p. (2021). MSC: 03D05 03B16 05C70 68Q25 68Q45 PDFBibTeX XMLCite \textit{M. Bojańczyk} et al., Log. Methods Comput. Sci. 17, No. 1, Paper No. 5, 40 p. (2021; Zbl 1509.03119) Full Text: arXiv Link
Schmitt-Grohé, Stephanie; Uribe, Martín Deterministic debt cycles in open economies with flow collateral constraints. (English) Zbl 1458.91139 J. Econ. Theory 192, Article ID 105195, 39 p. (2021). MSC: 91B62 PDFBibTeX XMLCite \textit{S. Schmitt-Grohé} and \textit{M. Uribe}, J. Econ. Theory 192, Article ID 105195, 39 p. (2021; Zbl 1458.91139) Full Text: DOI
Grohe, Martin; Rattan, Gaurav; Seppelt, Tim Homomorphism Tensors and Linear Equations. arXiv:2111.11313 Preprint, arXiv:2111.11313 [math.CO] (2021). MSC: 05C60 05C76 05C05 05C38 05C50 05E10 20M32 BibTeX Cite \textit{M. Grohe} et al., ``Homomorphism Tensors and Linear Equations'', Preprint, arXiv:2111.11313 [math.CO] (2021) Full Text: DOI arXiv OA License
Grohe, Martin; Kiefer, Sandra Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. arXiv:2106.16218 Preprint, arXiv:2106.16218 [cs.DM] (2021). BibTeX Cite \textit{M. Grohe} and \textit{S. Kiefer}, ``Logarithmic Weisfeiler-Leman Identifies All Planar Graphs'', Preprint, arXiv:2106.16218 [cs.DM] (2021) Full Text: arXiv OA License
Grohe, Martin; Lindner, Peter Infinite probabilistic databases. (English) Zbl 07650994 Lutz, Carsten (ed.) et al., 23rd international conference on database theory, ICDT 2020, Copenhagen, Denmark, March 30 – April 2, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 155, Article 16, 20 p. (2020). MSC: 68P15 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{P. Lindner}, LIPIcs -- Leibniz Int. Proc. Inform. 155, Article 16, 20 p. (2020; Zbl 07650994) Full Text: DOI arXiv
Grohe, Martin Weisfeiler and Leman’s unlikely journey from graph isomorphism to neural networks (invited talk). (English) Zbl 07650887 Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 2, 1 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{M. Grohe}, LIPIcs -- Leibniz Int. Proc. Inform. 154, Article 2, 1 p. (2020; Zbl 07650887) Full Text: DOI
Grohe, Martin; Neuen, Daniel; Schweitzer, Pascal; Wiebking, Daniel An improved isomorphism test for bounded-tree-width graphs. (English) Zbl 1484.68161 ACM Trans. Algorithms 16, No. 3, Article No. 34, 31 p. (2020). MSC: 68R10 05C25 05C60 05C85 68W40 PDFBibTeX XMLCite \textit{M. Grohe} et al., ACM Trans. Algorithms 16, No. 3, Article No. 34, 31 p. (2020; Zbl 1484.68161) Full Text: DOI Link
Grohe, Martin Counting bounded tree depth homomorphisms. (English) Zbl 1498.05135 Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 507-520 (2020). MSC: 05C30 05C60 03C13 PDFBibTeX XMLCite \textit{M. Grohe}, in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 507--520 (2020; Zbl 1498.05135) Full Text: DOI arXiv
Grohe, Martin; Schweitzer, Pascal; Wiebking, Daniel Automorphism groups of graphs of bounded Hadwiger number. arXiv:2012.14300 Preprint, arXiv:2012.14300 [math.CO] (2020). MSC: 05C75 05C83 20D60 BibTeX Cite \textit{M. Grohe} et al., ``Automorphism groups of graphs of bounded Hadwiger number'', Preprint, arXiv:2012.14300 [math.CO] (2020) Full Text: arXiv OA License
Böker, Jan; Chen, Yijia; Grohe, Martin; Rattan, Gaurav The complexity of homomorphism indistinguishability. (English) Zbl 07561698 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 54, 13 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{J. Böker} et al., LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 54, 13 p. (2019; Zbl 07561698) Full Text: DOI
Grohe, Martin; Kiefer, Sandra A linear upper bound on the weisfeiler-Leman dimension of graphs of bounded genus. (English) Zbl 07561610 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 117, 15 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{M. Grohe} and \textit{S. Kiefer}, LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 117, 15 p. (2019; Zbl 07561610) Full Text: DOI arXiv
Grohe, Martin Symmetry and similarity (Invited Talk). (English) Zbl 07561495 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 2, 1 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{M. Grohe}, LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 2, 1 p. (2019; Zbl 07561495) Full Text: DOI
Grädel, Erich; Grohe, Martin; Pago, Benedikt; Pakusa, Wied A finite-model-theoretic view on propositional proof complexity. (English) Zbl 1451.03023 Log. Methods Comput. Sci. 15, No. 1, Paper No. 4, 53 p. (2019). MSC: 03C13 03F20 68Q19 PDFBibTeX XMLCite \textit{E. Grädel} et al., Log. Methods Comput. Sci. 15, No. 1, Paper No. 4, 53 p. (2019; Zbl 1451.03023) Full Text: arXiv
Grohe, Martin; Rattan, Gaurav; Woeginger, Gerhard J. Graph similarity and approximate isomorphism. (English) Zbl 1510.68076 Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 20, 16 p. (2018). MSC: 68R10 05C50 05C60 05C85 68Q17 68Q25 68Q27 PDFBibTeX XMLCite \textit{M. Grohe} et al., LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 20, 16 p. (2018; Zbl 1510.68076) Full Text: DOI arXiv
Grohe, Martin; Neuen, Daniel; Schweitzer, Pascal; Wiebking, Daniel An improved isomorphism test for bounded-tree-width graphs. (English) Zbl 1484.68162 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 67, 14 p. (2018). MSC: 68R10 05C25 05C60 05C85 68W40 PDFBibTeX XMLCite \textit{M. Grohe} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 67, 14 p. (2018; Zbl 1484.68162) Full Text: DOI arXiv
Dell, Holger; Grohe, Martin; Rattan, Gaurav Lovász meets Weisfeiler and Leman. (English) Zbl 1504.05276 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 40, 14 p. (2018). MSC: 05C85 05C60 PDFBibTeX XMLCite \textit{H. Dell} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 40, 14 p. (2018; Zbl 1504.05276) Full Text: DOI arXiv
Bojańczyk, Mikołaj; Grohe, Martin; Pilipczuk, Michał Definable decompositions for graphs of bounded linear cliquewidth. (English) Zbl 1452.03088 Proceedings of the 2018 33rd annual ACM/IEEE symposium on logic in computer science, LICS 2018, Oxford, UK, July 9–12, 2018. New York, NY: Association for Computing Machinery (ACM). 135-144 (2018). MSC: 03D05 03B16 05C70 68Q25 68Q45 PDFBibTeX XMLCite \textit{M. Bojańczyk} et al., in: Proceedings of the 2018 33rd annual ACM/IEEE symposium on logic in computer science, LICS 2018, Oxford, UK, July 9--12, 2018. New York, NY: Association for Computing Machinery (ACM). 135--144 (2018; Zbl 1452.03088) Full Text: DOI arXiv
Grohe, Martin; Kreutzer, Stephan; Rabinovich, Roman; Siebertz, Sebastian; Stavropoulos, Konstantinos Coloring and covering nowhere dense graphs. (English) Zbl 1398.05121 SIAM J. Discrete Math. 32, No. 4, 2467-2481 (2018). MSC: 05C42 05C15 05C75 05C83 05C90 68Q17 PDFBibTeX XMLCite \textit{M. Grohe} et al., SIAM J. Discrete Math. 32, No. 4, 2467--2481 (2018; Zbl 1398.05121) Full Text: DOI
Arifovic, Jasmina; Schmitt-Grohé, Stephanie; Uribe, Martín Learning to live in a liquidity trap. (English) Zbl 1401.91304 J. Econ. Dyn. Control 89, 120-136 (2018). MSC: 91B64 PDFBibTeX XMLCite \textit{J. Arifovic} et al., J. Econ. Dyn. Control 89, 120--136 (2018; Zbl 1401.91304) Full Text: DOI Link
Schmitt-Grohé, Stephanie; Uribe, Martín How important are terms-of-trade shocks? (English) Zbl 1403.91240 Int. Econ. Rev. 59, No. 1, 85-111 (2018). MSC: 91B60 91B62 62J05 62P20 PDFBibTeX XMLCite \textit{S. Schmitt-Grohé} and \textit{M. Uribe}, Int. Econ. Rev. 59, No. 1, 85--111 (2018; Zbl 1403.91240) Full Text: DOI Link
Grohe, Martin; Pakusa, Wied Descriptive complexity of linear equation systems and applications to propositional proof complexity. (English) Zbl 1462.68075 Proceedings of the 2017 32nd annual ACM/IEEE symposium on logic in computer science, LICS 2017, Reykjavík University, Reykjavík, Iceland, June 20–23, 2017. Piscataway, NJ: IEEE Press. Article No. 21, 12 p. (2017). MSC: 68Q19 03F20 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{W. Pakusa}, in: Proceedings of the 2017 32nd annual ACM/IEEE symposium on logic in computer science, LICS 2017, Reykjavík University, Reykjavík, Iceland, June 20--23, 2017. Piscataway, NJ: IEEE Press. Article No. 21, 12 p. (2017; Zbl 1462.68075) Full Text: Link
Grohe, Martin; Ritzert, Martin Learning first-order definable concepts over structures of small degree. (English) Zbl 1457.68133 Proceedings of the 2017 32nd annual ACM/IEEE symposium on logic in computer science, LICS 2017, Reykjavík University, Reykjavík, Iceland, June 20–23, 2017. Piscataway, NJ: IEEE Press. Article No. 20, 12 p. (2017). MSC: 68Q32 03B70 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{M. Ritzert}, in: Proceedings of the 2017 32nd annual ACM/IEEE symposium on logic in computer science, LICS 2017, Reykjavík University, Reykjavík, Iceland, June 20--23, 2017. Piscataway, NJ: IEEE Press. Article No. 20, 12 p. (2017; Zbl 1457.68133) Full Text: arXiv Link
Grohe, Martin; Löding, Christof; Ritzert, Martin Learning MSO-definable hypotheses on strings. (English) Zbl 1403.68094 Hanneke, Steve (ed.) et al., International conference on algorithmic learning theory. Proceedings of the 28th conference (ALT 2017), Kyoto University, Kyoto, Japan, October 15–17, 2017. [s.l.]: Proceedings of Machine Learning Research PMLR. Proceedings of Machine Learning Research (PMLR) 76, 434-451 (2017). MSC: 68Q32 03B70 PDFBibTeX XMLCite \textit{M. Grohe} et al., Proc. Mach. Learn. Res. (PMLR) 76, 434--451 (2017; Zbl 1403.68094) Full Text: arXiv Link
Berkholz, Christoph; Grohe, Martin Linear Diophantine equations, group CSPs, and graph isomorphism. (English) Zbl 1410.68153 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 327-339 (2017). MSC: 68Q25 05C60 11D04 68Q17 PDFBibTeX XMLCite \textit{C. Berkholz} and \textit{M. Grohe}, in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 327--339 (2017; Zbl 1410.68153) Full Text: DOI arXiv
Grohe, Martin; Kreutzer, Stephan; Siebertz, Sebastian Deciding first-order properties of nowhere dense graphs. (English) Zbl 1426.68172 J. ACM 64, No. 3, Article No. 17, 32 p. (2017). MSC: 68Q60 05C75 68Q19 68R10 PDFBibTeX XMLCite \textit{M. Grohe} et al., J. ACM 64, No. 3, Article No. 17, 32 p. (2017; Zbl 1426.68172) Full Text: DOI arXiv
Chen, Yijia; Grohe, Martin; Lin, Bingkai The hardness of embedding grids and walls. (English) Zbl 1483.05176 Bodlaender, Hans L. (ed.) et al., Graph-theoretic concepts in computer science. 43rd international workshop, WG 2017, Eindhoven, The Netherlands, June 21–23, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10520, 180-192 (2017). MSC: 05C85 05C60 68Q25 PDFBibTeX XMLCite \textit{Y. Chen} et al., Lect. Notes Comput. Sci. 10520, 180--192 (2017; Zbl 1483.05176) Full Text: DOI arXiv
Berkholz, Christoph; Bonsma, Paul; Grohe, Martin Tight lower and upper bounds for the complexity of canonical colour refinement. (English) Zbl 1368.68219 Theory Comput. Syst. 60, No. 4, 581-614 (2017). MSC: 68Q25 05C15 05C60 05C85 PDFBibTeX XMLCite \textit{C. Berkholz} et al., Theory Comput. Syst. 60, No. 4, 581--614 (2017; Zbl 1368.68219) Full Text: DOI arXiv
Grohe, Martin Descriptive complexity, canonisation, and definable graph structure theory. (English) Zbl 06722029 Lecture Notes in Logic 47. Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL) (ISBN 978-1-107-01452-7/hbk; 978-1-139-02886-8/ebook). ix, 543 p. (2017). MSC: 68-02 03C13 03D15 05-02 05C60 05C75 05C83 68Q19 PDFBibTeX XMLCite \textit{M. Grohe}, Descriptive complexity, canonisation, and definable graph structure theory. Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL) (2017; Zbl 06722029) Full Text: DOI
Elberfeld, Michael; Frickenschmidt, Marlin; Grohe, Martin Order invariance on decomposable structures. (English) Zbl 1394.03056 Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 397-406 (2016). MSC: 03C13 03B10 03B15 05C05 05C10 PDFBibTeX XMLCite \textit{M. Elberfeld} et al., in: Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5--8, 2016. New York, NY: Association for Computing Machinery (ACM). 397--406 (2016; Zbl 1394.03056) Full Text: DOI arXiv
Grohe, Martin Quasi-4-connected components. (English) Zbl 1388.05101 Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 8, 13 p. (2016). MSC: 05C40 05C70 05C85 PDFBibTeX XMLCite \textit{M. Grohe}, LIPIcs -- Leibniz Int. Proc. Inform. 55, Article 8, 13 p. (2016; Zbl 1388.05101) Full Text: DOI arXiv
Elberfeld, Michael; Grohe, Martin; Tantau, Till Where first-order and monadic second-order logic coincide. (English) Zbl 1407.03003 ACM Trans. Comput. Log. 17, No. 4, Article No. 25, 18 p. (2016). MSC: 03B15 03B10 05C75 PDFBibTeX XMLCite \textit{M. Elberfeld} et al., ACM Trans. Comput. Log. 17, No. 4, Article No. 25, 18 p. (2016; Zbl 1407.03003) Full Text: DOI arXiv
Grohe, Martin; Kreutzer, Stephan; Rabinovich, Roman; Siebertz, Sebastian; Stavropoulos, Konstantinos Colouring and covering nowhere dense graphs. (English) Zbl 1417.05067 Mayr, Ernst W. (ed.), Graph-theoretic concepts in computer science. 41st international workshop, WG 2015, Garching, Germany, June 17–19, 2015. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 9224, 325-338 (2016). MSC: 05C15 05C42 05C70 68Q17 PDFBibTeX XMLCite \textit{M. Grohe} et al., Lect. Notes Comput. Sci. 9224, 325--338 (2016; Zbl 1417.05067) Full Text: DOI arXiv
Grohe, Martin; Schweitzer, Pascal Computing with tangles. (English) Zbl 1345.05101 SIAM J. Discrete Math. 30, No. 2, 1213-1247 (2016). MSC: 05C85 05C40 05C69 05C83 68P05 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{P. Schweitzer}, SIAM J. Discrete Math. 30, No. 2, 1213--1247 (2016; Zbl 1345.05101) Full Text: DOI
Grohe, Martin Tangles and connectivity in graphs. (English) Zbl 1442.05114 Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 10th international conference, LATA 2016, Prague, Czech Republic, March 14–18, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9618, 24-41 (2016). MSC: 05C40 68R10 PDFBibTeX XMLCite \textit{M. Grohe}, Lect. Notes Comput. Sci. 9618, 24--41 (2016; Zbl 1442.05114) Full Text: DOI arXiv
Grohe, Martin Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles). arXiv:1605.06704 Preprint, arXiv:1605.06704 [cs.DM] (2016). BibTeX Cite \textit{M. Grohe}, ``Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles)'', Preprint, arXiv:1605.06704 [cs.DM] (2016) Full Text: arXiv OA License
Grohe, Martin; Otto, Martin Pebble games and linear equations. (English) Zbl 1353.03018 J. Symb. Log. 80, No. 3, 797-844 (2015). MSC: 03C13 05C60 90C05 91A43 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{M. Otto}, J. Symb. Log. 80, No. 3, 797--844 (2015; Zbl 1353.03018) Full Text: DOI arXiv Link
Berkholz, Christoph; Grohe, Martin Limitations of algebraic approaches to graph isomorphism testing. (English) Zbl 1410.68152 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 155-166 (2015). MSC: 68Q25 05C25 05C60 13P10 68Q17 68W30 PDFBibTeX XMLCite \textit{C. Berkholz} and \textit{M. Grohe}, Lect. Notes Comput. Sci. 9134, 155--166 (2015; Zbl 1410.68152) Full Text: DOI arXiv
Grädel, Erich; Grohe, Martin Is polynomial time choiceless? (English) Zbl 1465.68100 Beklemishev, Lev D. (ed.) et al., Fields of logic and computation II. Essays dedicated to Yuri Gurevich on the occasion of his 75th birthday. Cham: Springer. Lect. Notes Comput. Sci. 9300, 193-209 (2015). MSC: 68Q19 03C13 PDFBibTeX XMLCite \textit{E. Grädel} and \textit{M. Grohe}, Lect. Notes Comput. Sci. 9300, 193--209 (2015; Zbl 1465.68100) Full Text: DOI
Grohe, Martin; Schweitzer, Pascal Computing with tangles. (English) Zbl 1321.05264 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 683-692 (2015). MSC: 05C85 05C40 05C69 05C83 68P05 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{P. Schweitzer}, in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 683--692 (2015; Zbl 1321.05264) Full Text: DOI arXiv
Grohe, Martin; Marx, Dániel Structure theorem and isomorphism test for graphs with excluded topological subgraphs. (English) Zbl 1314.05134 SIAM J. Comput. 44, No. 1, 114-159 (2015). MSC: 05C60 05C75 05C83 05C85 68R10 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{D. Marx}, SIAM J. Comput. 44, No. 1, 114--159 (2015; Zbl 1314.05134) Full Text: DOI
Grohe, Martin; Schweitzer, Pascal Isomorphism Testing for Graphs of Bounded Rank Width. arXiv:1505.03737 Preprint, arXiv:1505.03737 [cs.DM] (2015). BibTeX Cite \textit{M. Grohe} and \textit{P. Schweitzer}, ``Isomorphism Testing for Graphs of Bounded Rank Width'', Preprint, arXiv:1505.03737 [cs.DM] (2015) Full Text: arXiv OA License
Grohe, Martin; Marx, Dániel Constraint solving via fractional edge covers. (English) Zbl 1398.68240 ACM Trans. Algorithms 11, No. 1, Article No. 4, 20 p. (2014). MSC: 68Q25 05C65 05C70 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{D. Marx}, ACM Trans. Algorithms 11, No. 1, Article No. 4, 20 p. (2014; Zbl 1398.68240) Full Text: DOI arXiv
Grohe, Martin; Kreutzer, Stephan; Siebertz, Sebastian Deciding first-order properties of nowhere dense graphs. (English) Zbl 1315.05118 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 89-98 (2014). MSC: 05C75 03B25 05C42 05C57 PDFBibTeX XMLCite \textit{M. Grohe} et al., in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 89--98 (2014; Zbl 1315.05118) Full Text: DOI arXiv
Abu Zaid, F.; Grädel, E.; Grohe, M.; Pakusa, W. Choiceless polynomial time on structures with small abelian colour classes. (English) Zbl 1426.68106 Csuhaj-Varjú, Erzsébet (ed.) et al., Mathematical foundations of computer science 2014. 39th international symposium, MFCS 2014, Budapest, Hungary, August 25–29, 2014. Proceedings, Part I. Berlin: Springer. Lect. Notes Comput. Sci. 8634, 50-62 (2014). MSC: 68Q19 03C13 68Q15 PDFBibTeX XMLCite \textit{F. Abu Zaid} et al., Lect. Notes Comput. Sci. 8634, 50--62 (2014; Zbl 1426.68106) Full Text: DOI
Grohe, Martin; Kersting, Kristian; Mladenov, Martin; Selman, Erkal Dimension reduction via colour refinement. (English) Zbl 1425.68313 Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 505-516 (2014). MSC: 68R10 05C15 05C50 05C60 05C70 05C85 68W05 90C05 PDFBibTeX XMLCite \textit{M. Grohe} et al., Lect. Notes Comput. Sci. 8737, 505--516 (2014; Zbl 1425.68313) Full Text: DOI arXiv
Grohe, Martin Algorithmic meta theorems for sparse graph classes. (English) Zbl 1407.68529 Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. 9th international computer science symposium in Russia, CSR 2014, Moscow, Russia, June 7–11, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8476, 16-22 (2014). MSC: 68W01 03B25 68R10 PDFBibTeX XMLCite \textit{M. Grohe}, Lect. Notes Comput. Sci. 8476, 16--22 (2014; Zbl 1407.68529) Full Text: DOI
Grohe, Martin; Kawarabayashi, Ken-ichi; Reed, Bruce A simple algorithm for the graph minor decomposition – logic meets structural graph theory. (English) Zbl 1423.05159 Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 414-431 (2013). MSC: 05C83 05C05 05C70 PDFBibTeX XMLCite \textit{M. Grohe} et al., in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6--8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 414--431 (2013; Zbl 1423.05159) Full Text: DOI Link
Grohe, Martin Bounds and algorithms for joins via fractional edge covers. (English) Zbl 1397.68046 Tannen, Val (ed.) et al., In search of elegance in the theory and practice of computation. Essays dedicated to Peter Buneman. Berlin: Springer (ISBN 978-3-642-41659-0/pbk; 978-3-642-41660-6/ebook). Lecture Notes in Computer Science 8000, 321-338 (2013). MSC: 68P15 PDFBibTeX XMLCite \textit{M. Grohe}, Lect. Notes Comput. Sci. 8000, 321--338 (2013; Zbl 1397.68046) Full Text: DOI
Grohe, Martin; Kreutzer, Stephan; Siebertz, Sebastian Characterisations of nowhere dense graphs (invited talk). (English) Zbl 1359.05102 Seth, Anil (ed.) et al., 33nd international conference on foundations of software technology and theoretical computer science, FSTTCS 2013, Guwahati, India, December 12–14, 2013. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-64-4). LIPIcs – Leibniz International Proceedings in Informatics 24, 21-40 (2013). MSC: 05C75 05C85 PDFBibTeX XMLCite \textit{M. Grohe} et al., LIPIcs -- Leibniz Int. Proc. Inform. 24, 21--40 (2013; Zbl 1359.05102) Full Text: DOI
Atserias, Albert; Grohe, Martin; Marx, Dániel Size bounds and query plans for relational joins. (English) Zbl 1276.68066 SIAM J. Comput. 42, No. 4, 1737-1767 (2013). MSC: 68P15 68Q25 90C05 PDFBibTeX XMLCite \textit{A. Atserias} et al., SIAM J. Comput. 42, No. 4, 1737--1767 (2013; Zbl 1276.68066) Full Text: DOI arXiv
Berkholz, Christoph; Bonsma, Paul; Grohe, Martin Tight lower and upper bounds for the complexity of canonical colour refinement. (English) Zbl 1362.68097 Bodlaender, Hans L. (ed.) et al., Algorithms – ESA 2013. 21st annual European symposium, Sophia Antipolis, France, September 2–4, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40449-8/pbk). Lecture Notes in Computer Science 8125, 145-156 (2013). MSC: 68Q25 05C15 05C60 05C85 PDFBibTeX XMLCite \textit{C. Berkholz} et al., Lect. Notes Comput. Sci. 8125, 145--156 (2013; Zbl 1362.68097) Full Text: DOI Link
Grohe, Martin; Grußien, Berit; Hernich, André; Laubner, Bastian L-recursion and a new logic for logarithmic space. (English) Zbl 1260.68168 Log. Methods Comput. Sci. 9, No. 1, Paper No. 12, 44 p. (2013). MSC: 68Q19 03B70 PDFBibTeX XMLCite \textit{M. Grohe} et al., Log. Methods Comput. Sci. 9, No. 1, Paper No. 12, 44 p. (2013; Zbl 1260.68168) Full Text: DOI
Elberfeld, Michael; Grohe, Martin; Tantau, Till Where first-order and monadic second-order logic coincide. (English) Zbl 1364.03015 Proceedings of the 2012 27th annual ACM/IEEE symposium on logic in computer science, LICS 2012, Dubrovnik, Croatia, June 25–28, 2012. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4769-5). 265-274 (2012). MSC: 03B15 03B10 05C75 PDFBibTeX XMLCite \textit{M. Elberfeld} et al., in: Proceedings of the 2012 27th annual ACM/IEEE symposium on logic in computer science, LICS 2012, Dubrovnik, Croatia, June 25--28, 2012. Los Alamitos, CA: IEEE Computer Society. 265--274 (2012; Zbl 1364.03015) Full Text: DOI
Grohe, Martin; Marx, Dániel Structure theorem and isomorphism test for graphs with excluded topological subgraphs. (English) Zbl 1286.05106 Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 173-192 (2012). MSC: 05C60 05C83 05C05 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{D. Marx}, in: Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19--22, 2012. New York, NY: Association for Computing Machinery (ACM). 173--192 (2012; Zbl 1286.05106) Full Text: DOI arXiv
Grohe, Martin Fixed-point definability and polynomial time on graphs with excluded minors. (English) Zbl 1281.68129 J. ACM 59, No. 5, Article No. 27, 64 p. (2012). MSC: 68Q19 05C60 05C83 PDFBibTeX XMLCite \textit{M. Grohe}, J. ACM 59, No. 5, Article No. 27, 64 p. (2012; Zbl 1281.68129) Full Text: DOI
Schmitt-Grohé, Stephanie; Uribe, Martín What’s news in business cycles. (English) Zbl 1274.91324 Econometrica 80, No. 6, 2733-2764 (2012). MSC: 91B64 91B51 62P20 62F10 62F15 PDFBibTeX XMLCite \textit{S. Schmitt-Grohé} and \textit{M. Uribe}, Econometrica 80, No. 6, 2733--2764 (2012; Zbl 1274.91324) Full Text: DOI
Grohe, Martin; Otto, Martin Pebble games and linear equations. (English) Zbl 1252.03084 Cégielski, Patrick (ed.) et al., Computer science logic (CSL’12). 26th international workshop, 21th annual conference of the EACSL, September 3–6, 2012, Fontainebleau, France. Selected papers based on the presentations at the conference. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-42-2). LIPIcs – Leibniz International Proceedings in Informatics 16, 289-304, electronic only (2012). MSC: 03C13 05C60 90C05 91A43 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{M. Otto}, LIPIcs -- Leibniz Int. Proc. Inform. 16, 289--304 (2012; Zbl 1252.03084) Full Text: DOI
Schmitt-Grohé, Stephanie; Uribe, Martín An OLS approach to computing Ramsey equilibria in medium-scale macroeconomic models. (English) Zbl 1242.91112 Econ. Lett. 115, No. 1, 128-129 (2012). MSC: 91B51 PDFBibTeX XMLCite \textit{S. Schmitt-Grohé} and \textit{M. Uribe}, Econ. Lett. 115, No. 1, 128--129 (2012; Zbl 1242.91112) Full Text: DOI
Bulatov, Andrei A.; Dalmau, Víctor; Grohe, Martin; Marx, Dániel Enumerating homomorphisms. (English) Zbl 1253.68165 J. Comput. Syst. Sci. 78, No. 2, 638-650 (2012). MSC: 68Q25 05C30 68R05 PDFBibTeX XMLCite \textit{A. A. Bulatov} et al., J. Comput. Syst. Sci. 78, No. 2, 638--650 (2012; Zbl 1253.68165) Full Text: DOI
Grohe, Martin; Kawarabayashi, Ken-ichi; Marx, Dániel; Wollan, Paul Finding topological subgraphs is fixed-parameter tractable. (English) Zbl 1288.05058 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 479-488 (2011). MSC: 05C10 05C83 05C85 68Q25 PDFBibTeX XMLCite \textit{M. Grohe} et al., in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 479--488 (2011; Zbl 1288.05058) Full Text: DOI arXiv Link
Grohe, Martin; Grußien, Berit; Hernich, André; Laubner, Bastian L-recursion and a new logic for logarithmic space. (English) Zbl 1247.68104 Bezem, Marc (ed.), Computer science logic (CSL’11). 25th international workshop, 20th annual conference of the EACSL, Bergen, Norway, September 12–15, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-32-3). LIPIcs – Leibniz International Proceedings in Informatics 12, 277-291, electronic only (2011). MSC: 68Q19 03B70 PDFBibTeX XMLCite \textit{M. Grohe} et al., LIPIcs -- Leibniz Int. Proc. Inform. 12, 277--291 (2011; Zbl 1247.68104) Full Text: DOI arXiv Link
Eickmeyer, Kord; Grohe, Martin Randomisation and derandomisation in descriptive complexity theory. (English) Zbl 1237.68093 Log. Methods Comput. Sci. 7, No. 3, Paper No. 14, 24 p. (2011). MSC: 68Q19 03C13 68Q15 68Q87 PDFBibTeX XMLCite \textit{K. Eickmeyer} and \textit{M. Grohe}, Log. Methods Comput. Sci. 7, No. 3, Paper No. 14, 24 p. (2011; Zbl 1237.68093) Full Text: DOI
Grohe, Martin; Thurley, Marc Counting homomorphisms and partition functions. (English) Zbl 1255.68071 Grohe, Martin (ed.) et al., Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5–8, 2009. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4943-9/pbk). Contemporary Mathematics 558, 243-291 (2011). MSC: 68Q17 03C30 05C30 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{M. Thurley}, Contemp. Math. 558, 243--291 (2011; Zbl 1255.68071)
Grohe, Martin; Kreutzer, Stephan Methods for algorithmic meta theorems. (English) Zbl 1278.68099 Grohe, Martin (ed.) et al., Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5–8, 2009. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4943-9/pbk). Contemporary Mathematics 558, 181-205 (2011). Reviewer: Galina Jiraskova (Košice) MSC: 68Q19 68Q25 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{S. Kreutzer}, Contemp. Math. 558, 181--205 (2011; Zbl 1278.68099)
Grohe, Martin (ed.); Makowsky, Johann A. (ed.) Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5–8, 2009. (English) Zbl 1230.03009 Contemporary Mathematics 558. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4943-9/pbk). viii, 519 p. (2011). MSC: 03-06 05-06 68-06 03C65 05Axx 05Cxx 68Q19 00B25 PDFBibTeX XMLCite \textit{M. Grohe} (ed.) and \textit{J. A. Makowsky} (ed.), Model theoretic methods in finite combinatorics. AMS-ASL joint special session, Washington, DC, USA, January 5--8, 2009. Providence, RI: American Mathematical Society (AMS) (2011; Zbl 1230.03009) Full Text: DOI
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc A complexity dichotomy for partition functions with mixed signs. (English) Zbl 1298.68099 SIAM J. Comput. 39, No. 7, 3336-3402 (2010). Reviewer: Klaus Dohmen (Mittweida) MSC: 68Q17 68Q25 68R05 68R10 05C31 PDFBibTeX XMLCite \textit{L. A. Goldberg} et al., SIAM J. Comput. 39, No. 7, 3336--3402 (2010; Zbl 1298.68099) Full Text: DOI Link
Schmitt-Grohé, Stephanie; Uribe, Martín Evaluating the sample likelihood of linearized DSGE models without the use of the Kalman filter. (English) Zbl 1203.91152 Econ. Lett. 109, No. 3, 142-143 (2010). MSC: 91B51 91B82 62P20 PDFBibTeX XMLCite \textit{S. Schmitt-Grohé} and \textit{M. Uribe}, Econ. Lett. 109, No. 3, 142--143 (2010; Zbl 1203.91152) Full Text: DOI
Chen, Hubie; Grohe, Martin Constraint satisfaction with succinctly specified relations. (English) Zbl 1214.68347 J. Comput. Syst. Sci. 76, No. 8, 847-860 (2010). MSC: 68T20 PDFBibTeX XMLCite \textit{H. Chen} and \textit{M. Grohe}, J. Comput. Syst. Sci. 76, No. 8, 847--860 (2010; Zbl 1214.68347) Full Text: DOI Link
Eickmeyer, Kord; Grohe, Martin Randomisation and derandomisation in descriptive complexity theory. (English) Zbl 1287.68063 Dawar, Anuj (ed.) et al., Computer science logic. 24th international workshop, CSL 2010, 19th annual conference of the EACSL, Brno, Czech Republic, August 23–27, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15204-7/pbk). Lecture Notes in Computer Science 6247, 275-289 (2010). MSC: 68Q19 PDFBibTeX XMLCite \textit{K. Eickmeyer} and \textit{M. Grohe}, Lect. Notes Comput. Sci. 6247, 275--289 (2010; Zbl 1287.68063) Full Text: DOI arXiv
Grohe, Martin Fixed-point definability and polynomial time on chordal graphs and line graphs. (English) Zbl 1287.68064 Blass, Andreas (ed.) et al., Fields of logic and computation. Essays dedicated to Yuri Gurevich on the occasion of his 70th birthday. Berlin: Springer (ISBN 978-3-642-15024-1/pbk). Lecture Notes in Computer Science 6300, 328-353 (2010). MSC: 68Q19 03C13 68Q15 PDFBibTeX XMLCite \textit{M. Grohe}, Lect. Notes Comput. Sci. 6300, 328--353 (2010; Zbl 1287.68064) Full Text: DOI arXiv
Grohe, Martin; Hernich, André; Schweikardt, Nicole Lower bounds for processing data with few random accesses to external memory. (English) Zbl 1325.68098 J. ACM 56, No. 3, Article No. 12, 58 p. (2009). MSC: 68Q17 68P10 68P15 68P20 PDFBibTeX XMLCite \textit{M. Grohe} et al., J. ACM 56, No. 3, Article No. 12, 58 p. (2009; Zbl 1325.68098) Full Text: DOI
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc A complexity dichotomy for partition functions with mixed signs. (English) Zbl 1236.68092 Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26–28, 2009. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPIcs – Leibniz International Proceedings in Informatics 3, 493-504, electronic only (2009). MSC: 68Q17 05C85 05C15 PDFBibTeX XMLCite \textit{L. A. Goldberg} et al., LIPIcs -- Leibniz Int. Proc. Inform. 3, 493--504 (2009; Zbl 1236.68092) Full Text: DOI Link
Bulatov, Andrei A.; Dalmau, Víctor; Grohe, Martin; Marx, Dániel Enumerating homomorphisms. (English) Zbl 1236.68105 Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26–28, 2009. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPIcs – Leibniz International Proceedings in Informatics 3, 231-242, electronic only (2009). MSC: 68Q25 05C30 68R05 PDFBibTeX XMLCite \textit{A. A. Bulatov} et al., LIPIcs -- Leibniz Int. Proc. Inform. 3, 231--242 (2009; Zbl 1236.68105) Full Text: DOI Link
Grohe, Martin Fixed-point definability and polynomial time. (English) Zbl 1257.68069 Grädel, Erich (ed.) et al., Computer science logic. 23rd international workshop, CSL 2009, 18th annual conference of the EACSL, Coimbra, Portugal, September 7–11, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04026-9/pbk). Lecture Notes in Computer Science 5771, 20-23 (2009). MSC: 68Q15 03B70 68Q19 PDFBibTeX XMLCite \textit{M. Grohe}, Lect. Notes Comput. Sci. 5771, 20--23 (2009; Zbl 1257.68069) Full Text: DOI
Grohe, Martin; Gurevich, Yuri; Leinders, Dirk; Schweikardt, Nicole; Tyszkiewicz, Jerzy; Van den Bussche, Jan Database query processing using finite cursor machines. (English) Zbl 1192.68213 Theory Comput. Syst. 44, No. 4, 533-560 (2009). MSC: 68P15 PDFBibTeX XMLCite \textit{M. Grohe} et al., Theory Comput. Syst. 44, No. 4, 533--560 (2009; Zbl 1192.68213) Full Text: DOI Link
Grohe, Martin; Schwandtner, Goetz The complexity of datalog on linear orders. (English) Zbl 1164.68008 Log. Methods Comput. Sci. 5, No. 1, Paper 5, 21 p. (2009). MSC: 68Q25 68N17 68P15 68Q17 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{G. Schwandtner}, Log. Methods Comput. Sci. 5, No. 1, Paper 5, 21 p. (2009; Zbl 1164.68008) Full Text: DOI arXiv
Grohe, Martin; Marx, Dániel On tree width, bramble size, and expansion. (English) Zbl 1205.05049 J. Comb. Theory, Ser. B 99, No. 1, 218-228 (2009). MSC: 05C05 05C70 68Q25 68W25 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{D. Marx}, J. Comb. Theory, Ser. B 99, No. 1, 218--228 (2009; Zbl 1205.05049) Full Text: DOI
Grohe, Martin Logic, graphs, and algorithms. (English) Zbl 1244.03053 Flum, Jörg (ed.) et al., Logic and automata. History and perspectives. Dedicated to Wolfgang Thomas on the occasion of his sixtieth birthday. Amsterdam: Amsterdam University Press (ISBN 978-90-5356-576-6/pbk). Texts in Logic and Games 2, 357-422 (2008). MSC: 03B25 05C85 68R10 68W01 PDFBibTeX XMLCite \textit{M. Grohe}, Texts Log. Games 2, 357--422 (2008; Zbl 1244.03053)
Adler, Isolde; Grohe, Martin; Kreutzer, Stephan Computing excluded minors. (English) Zbl 1192.68810 Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 641-650 (2008). MSC: 68W05 05C83 68R10 PDFBibTeX XMLCite \textit{I. Adler} et al., in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20--22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 641--650 (2008; Zbl 1192.68810)
Ravn, Morten O.; Schmitt-Grohé, Stephanie; Uribe, Martín Macroeconomics of subsistence points. (English) Zbl 1175.91118 Macroecon. Dyn. 12, Suppl. 1, 136-147 (2008). MSC: 91B64 PDFBibTeX XMLCite \textit{M. O. Ravn} et al., Macroecon. Dyn. 12, 136--147 (2008; Zbl 1175.91118) Full Text: DOI
Atserias, Albert; Dawar, Anuj; Grohe, Martin Preservation under extensions on well-behaved finite structures. (English) Zbl 1169.03025 SIAM J. Comput. 38, No. 4, 1364-1381 (2008). MSC: 03C13 03C40 03C52 68Q19 PDFBibTeX XMLCite \textit{A. Atserias} et al., SIAM J. Comput. 38, No. 4, 1364--1381 (2008; Zbl 1169.03025) Full Text: DOI
Bodirsky, Manuel; Grohe, Martin Non-dichotomies in constraint satisfaction complexity. (English) Zbl 1155.68403 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-70582-6/pbk). Lecture Notes in Computer Science 5126, 184-196 (2008). MSC: 68Q25 03B70 08A70 68Q15 68Q17 PDFBibTeX XMLCite \textit{M. Bodirsky} and \textit{M. Grohe}, Lect. Notes Comput. Sci. 5126, 184--196 (2008; Zbl 1155.68403) Full Text: DOI
Grohe, Martin (ed.); Niedermeier, Rolf (ed.) Parameterized and exact computation. Third international workshop, IWPEC 2008, Victoria, Canada, May 14–16, 2008. Proceedings. (English) Zbl 1137.68009 Lecture Notes in Computer Science 5018. Berlin: Springer (ISBN 978-3-540-79722-7/pbk). x, 227 p. (2008). MSC: 68-06 68Qxx 68Rxx 68Wxx 00B25 PDFBibTeX XMLCite \textit{M. Grohe} (ed.) and \textit{R. Niedermeier} (ed.), Parameterized and exact computation. Third international workshop, IWPEC 2008, Victoria, Canada, May 14--16, 2008. Proceedings. Berlin: Springer (2008; Zbl 1137.68009) Full Text: DOI
Grohe, Martin; Hyland, Martin; Makowsky, Johann A.; Niwinski, Damian The Ackermann Award 2007. (English) Zbl 1177.03006 Duparc, Jacques (ed.) et al., Computer science logic. 21st international workshop, CSL 2007, 16th annual conference of the EACSL, Lausanne, Switzerland, September 11–15, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74914-1/pbk). Lecture Notes in Computer Science 4646, 589-597 (2007). MSC: 03-03 68-03 01A99 03B70 03B35 03F03 PDFBibTeX XMLCite \textit{M. Grohe} et al., Lect. Notes Comput. Sci. 4646, 589--597 (2007; Zbl 1177.03006) Full Text: DOI
Grohe, Martin The complexity of homomorphism and constraint satisfaction problems seen from the other side. (English) Zbl 1312.68101 J. ACM 54, No. 1, Article No. 1, 24 p. (2007). MSC: 68Q25 05C75 08A02 68P15 68T20 PDFBibTeX XMLCite \textit{M. Grohe}, J. ACM 54, No. 1, Article No. 1, 24 p. (2007; Zbl 1312.68101) Full Text: DOI
Chen, Yijia; Grohe, Martin An isomorphism between subexponential and parameterized complexity theory. (English) Zbl 1154.03020 SIAM J. Comput. 37, No. 4, 1228-1258 (2007). Reviewer: Marius Zimand (Towson) MSC: 03D15 03D30 68Q17 68Q25 PDFBibTeX XMLCite \textit{Y. Chen} and \textit{M. Grohe}, SIAM J. Comput. 37, No. 4, 1228--1258 (2007; Zbl 1154.03020) Full Text: DOI
Dawar, Anuj; Grohe, Martin; Kreutzer, Stephan; Schweikardt, Nicole Model theory makes formulas large. (English) Zbl 1171.03324 Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 913-924 (2007). MSC: 03C07 03C13 03D15 PDFBibTeX XMLCite \textit{A. Dawar} et al., Lect. Notes Comput. Sci. 4596, 913--924 (2007; Zbl 1171.03324) Full Text: DOI
Grohe, Martin; Grüber, Magdalena Parameterized approximability of the disjoint cycle problem. (English) Zbl 1171.68869 Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 363-374 (2007). MSC: 68W25 05C38 68Q25 PDFBibTeX XMLCite \textit{M. Grohe} and \textit{M. Grüber}, Lect. Notes Comput. Sci. 4596, 363--374 (2007; Zbl 1171.68869) Full Text: DOI
Adler, Isolde; Gottlob, Georg; Grohe, Martin Hypertree width and related hypergraph invariants. (English) Zbl 1127.05065 Eur. J. Comb. 28, No. 8, 2167-2181 (2007). MSC: 05C65 PDFBibTeX XMLCite \textit{I. Adler} et al., Eur. J. Comb. 28, No. 8, 2167--2181 (2007; Zbl 1127.05065) Full Text: DOI