Logic in Computer Science Prof. Dr. Martin Grohe

Martin Grohe's Publications

Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs,

2009.

 

Fixed-Point Definability and Polynomial Time.

In Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), pp.20-23, 2009. Slides of my CSL-talk.

 

Logics with Rank Operators,

with Anuj Dawar, Bjarki Holm, and Bastian Laubner. In Proceedings of the 23rd 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,

with Andre Hernich and Nicole Schweikardt. Journal of the ACM, 56(3), 2009. Full version of PODS'05 and PODS'06 papers.

 

Database query processing using finite cursor machines,

with Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, and Jan Van den Bussche. Theory of Computing Systems, 44:533-560, 2009.
Conference version in In Proceedings of the 11th International Conference on Database Theory (ICDT'07), Lecture Notes in Computer Science 4353, pp.284-298, 2007.

 

The Complexity of Datalog on Linear Orders,

with Götz Schwandtner. Logical Methods in Computer Science, 5(1), 2009.

 

Enumerating Homomorphisms,

with Andrei A. Bulatov, Victor Dalmau, and Dániel Marx. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.231-242, 2009.

 

A complexity dichotomy for partition functions with mixed signs,

with Leslie Ann Goldberg, Mark Jerrum, and Marc Thurley. Conference version in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp.493-504, 2009.

 

On tree width, bramble size, and expansion,

with Dániel Marx. Journal of Combinatorial Theory, Series B 99:218-228, 2009.

 

Preservation under Extensions on Well-Behaved Finite Structures,

with Albert Atserias and Anuj Dawar. SIAM Journal on Computing, 38:1364-1381, 2008.
Conference version appeared in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lecture Notes in Computer Science 3580, pp.1437-1450, 2005. (Abstract)

 

Size bounds and query plans for relational joins,

with Albert Atserias and Dániel Marx. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'08), pp.739-748, 2008.

 

Non-dichotomies in constraint satisfaction complexity,

with Manuel Bodirsky. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08, Track B), Lecture Notes in Computer Science 5126, pp.184-196, 2008.

 

Definable tree decompositions.

In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.406-417, 2008.

 

The quest for a logic capturing PTIME.

In 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,

with Kord Eickmeyer and Magdalena Grüber. In Proceedings of the 23rd IEEE Conference on Computational Complexity (CCC'08), pp.8-18, 2008.

 

Computing excluded minors,

with Isolde Adler and Stephan Kreutzer. In Proceedings of the of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp.641-650, 2008.

 

Logic, graphs, and algorithms.

In J.Flum, E.Grädel, T.Wilke (Eds), Logic and Automata – History and Perspectives, Amsterdam University Press, 2007.

 

An Isomorphism between Subexponential and Parameterized Complexity Theory,

with Yijia Chen. SIAM Journal on Computing 37:1228-1258, 2007. Conference version in Proceedings of the 21st IEEE Conference on Computational Complexity (CCC'06), pp.314-328, 2006.

 

Bounded Fixed-Parameter Tractability and Reducibility,

with Rod Downey, Jörg Flum, and Mark Weyer. Annals of Pure and Applied Logic 148:1-19, 2007.

 

Parameterized Approximability of the Disjoint Cycle Problem ,

with Magdalena Grüber. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A), Lecture Notes in Computer Science 4596, pp.363-374, 2007.

 

Model Theory Makes Formulas Large,

with Anuj Dawar, Stephan Kreutzer and Nicole Schweikardt. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track B), Lecture Notes in Computer Science 4596, pp.913-924, 2007.

 

Locally Excluding a Minor,

with Anuj Dawar and Stephan Kreutzer. In 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.

Journal of the ACM, 54(1), 2007. Conference version in Proceedings of the 44th IEEE Symposium on Foundations of Comupter Science (FOCS'03), pp.552-561, 2003. (Abstract)

 

Hypertree-Width and Related Hypergraph Invariants,

with Isolde Adler and Georg Gottlob. European Journal of Combinatorics, 28:2167-2181, 2007.
Conference version in 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,

with Christoph Koch and Nicole Schweikardt. Theoretical Computer Science 380:199-217, 2007. Conference version in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lecture Notes in Computer Science 3580, pp.1076-1088, 2005. (Abstract)

 

An analysis of the W*-hierarchy,

with Yijia Chen and Jörg Flum. Journal of Symbolic Logic 72:513-534, 2007.

 

Constraint satisfaction problems with succinctly specified relations,

with Hubie Chen. Preliminary version in Dagstuhl Seminar Proceedings 06401: Complexity of Constraints, 2006.

 

On parameterized approximability ,

with Yijia Chen and Magdalena Grüber. Conference version appeared in Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science 4169, pp.109-120, 2006.

 

Approximation Schemes for First-Order Definable Optimisation Problems ,

with Anuj Dawar, Stephan Kreutzer, and Nicole Schweikardt. In Proceedings of the 21st IEEE Symposium on Logic in Computer Science, pp.411-420, 2006.

 

The structure of tractable constraint satisfaction problems .

In Proceedings of the 31st Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 4162, pp.58-72, 2006.

 

Testing Graph Isomorphism in Parallel by Playing a Game ,

with Oleg Verbitzky. Conference version in Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Part I, Lecture Notes in Computer Science 4051, pp.3-14, 2006.

 

Randomized Computations on Large Data Sets: Tight Lower Bounds,

with Andre Hernich and Nicole Schweikardt. In Proceedings of the 25th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'06), pp.243-252, 2006.

 

  Parameterized Complexity Theory,

with Jörg Flum. Springer-Verlag, 2006.

 

Constraint Solving via Fractional Edge Covers,

with Dániel Marx. In Proceedings of the of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp.289-298, 2006. (Abstract)

 

Bounded fixed-parameter tractability and log²n nondeterministic bits ,

with Jörg Flum and Mark Weyer. Journal of Computer and System Sciences 72:34-71, 2006.
Conference version in Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Lecture Notes in Computer Science 3142, pp.555-567, 2004. (Abstract)

 

The complexity of partition functions,

with Andrei Bulatov. Theoretical Computer Science 348:148-186, 2005.
Conference version in Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Lecture Notes in Computer Science 3142, pp. 294-306, 2004. (Abstract)

 

Hypertree Decompositions: Structure, Algorithms, and Applications,

with Georg Gottlob, Nysret Musliu, Marko Samer, and Francesco Scarcello Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05), Lecture Notes in Computer Science , pp.1-15, 2005. (Abstract)

 

The expressive power of two-variable least fixed-point logics,

with Stephan Kreutzer and Nicole Schweikardt. Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS'05), Lecture Notes in Computer Science , pp.422-434, 2005. (Abstract)

 

The succinctness of first-order logic on linear orders,

with Nicole Schweikardt. Logical Methods in Computer Science, 1(1), 2005.
Conference version in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pp. 438-447, 2004.

 

Machine-based methods in parameterized complexity theory,

with Yijia Chen and Jörg Flum. Theoretical Computer Science., 339:167-199, 2005. (Abstract)

 

The complexity of querying external memory and streaming data,

with Christoph Koch and Nicole Schweikardt. Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT'05), Lecture Notes in Computer Science 3623, pp.1-16, 2005. (Abstract)

 

Lower Bounds for Sorting with Few Random Accesses to External Memory,

with Nicole Schweikardt. In Proceedings of the 24th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS'05), pp.238-249, 2005. (Abstract)

 

Model-Checking Problems as a Basis for Parameterized Intractability,

with Jörg Flum. Logical Methods in Computer Science 1(1), 2005.
Conference version in 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,

with Markus Frick. Annals of Pure and Applied Logic 130: 3-31, 2004. (Abstract)
Conference version in Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02), pp. 215-224, 2002.

 

Parameterized Complexity and Subexponential Time,

with Jörg Flum. Bulletin of the European Association for Theoretical Computer Science 84, October 2004.

 

The parameterized complexity of counting problems,

with Jörg Flum. SIAM Journal on Computing 33:892-922, 2004. (Abstract)
Conference version in Proceedings of the 43rd IEEE Symposium on Foundations of Comupter Science (FOCS'02), pp. 538-547, 2002.

 

An Existential Locality Theorem ,

with Stefan Wöhrle. Annals of Pure and Applied Logic, 129: 131-148, 2004. (Abstract)
Conference Version in 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.

 

Computing Crossing Numbers in Quadratic Time .

Journal of Computer and System Sciences, 68(2):285-302, 2004. (Abstract)
Conference version in Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.231-236, 2001.

 

Learnability and Definability in Trees and Similar Structures ,

with Gyorgy Turan. Theory of Computing Systems 37(1):193-220, 2004. (Abstract)
Conference version in 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.

Combinatorica 23(4):613-632, 2003. (Abstract)

 

Describing Parameterized Complexity Classes ,

with Jörg Flum. Information and Computation 187: 291-319, 2003. (Abstract)
Conference version in 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,

with Nicole Schweikardt. RAIRO - Theoretical Informatics and Applications (ITA) 38:343-373, 2004.
Conference version in Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03), Lecture Notes in Computer Science 2803, pp.226-240, 2003. (Abstract)

 

Path Queries on Compressed XML,

with Peter Buneman and Christoph Koch. In Proceedings of the 29th Conference on Very Large Data Bases (VLDB 2003), pp.141-152, 2003.

 

Query Evaluation on Compressed Trees,

with Markus Frick and 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,

with Yijia Chen and Jörg Flum. In Proceedings of the 18th IEEE Conference on Computational Complexity (CCC'03), pp.13-29, 2003. (Abstract)

 

Reachability and Connectivity Queries in Constraint Databases,

with Michael Benedikt, Leonid Libkin, and Luc Segoufin. Journal of Computer System Sciences 66(1):169-206, 2003. (Abstract)
Conference version in Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS'00), 2000.

 

Parameterized Complexity for the Database Theorist,

SIGMOD Record 31(4), 2002.

 

Query evaluation via tree-decompositions ,

with Jörg Flum and Markus Frick. Journal of the ACM 49:716-752, 2002. (Abstract)
Conference version in Proceedings of the 8th International Conference on Database Theory. Lecture Notes in Computer Science 1973, Springer-Verlag, 2001.

 

On first-order topological queries ,

with Luc Segoufin. ACM Transactions on Computational Logic 3(3):336-358, 2002. (Abstract)
Conference version in Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 2000.

 

Large finite structures with few L^k-types.

Information and Computation 179(2): 250-278, 2002.
Conference Version in Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, 1997. (Abstract)

 

When is the evaluation of conjunctive queries tractable ?,

with Thomas Schwentick and Luc Segoufin. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC'01), pp.657-666, 2001. (Abstract)

 

The Parameterized Complexity of Database Queries,

In Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'01), pp.82-92, 2001. (Abstract)

 

Fixed-parameter tractability, definability, and model checking,

with Jörg Flum. SIAM Journal on Computing 31:113-145, 2001. (Abstract)

 

Generalized model-checking problems for first-order logic.

In 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. (Abstract)

 

Deciding first-order properties of locally tree-decomposable structures,

with Markus Frick. Journal of the ACM 48:1184-1206, 2001.
Conference version in 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.

Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000. (Abstract)

 

Locality of order-invariant first-order formulas,

with Thomas Schwentick. ACM Transactions on Computational Logic 1:112-130, 2000.
Conference version in Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science 1450, Springer-Verlag, 1998. (Abstract)

 

On fixed-point logic with counting,

with Jörg Flum, 1998. Journal of Symbolic Logic 65:777-787, 2000.

 

Equivalence in finite-variable logics is complete for polynomial time.

Combinatorica 19:507-532, 1999.

 

Descriptive and parameterized complexity,

In Computer Science Logic, 13th Workshop (CSL'99). Lecture Notes in Computer Science 1683, Springer-Verlag, 1999. (Abstract)

 

Definability and descriptive complexity on databases of bounded tree-width,

with Julian Marino. In Proceedings of the 7th International Conference on Database Theory (ICDT'99). Lecture Notes in Computer Science 1540, Springer-Verlag, 1999. (Abstract)

 

Zur Struktur dessen, was wirklich berechenbar ist,

with Heinz-Dieter Ebbinghaus. Philosophia Naturalis 36:91-116, 1999.

 

Finite variable logics in descriptive complexity theory,

Bulletin of Symbolic Logic 4:345-398, 1998.

 

Fixed-point logics on planar graphs,

in Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS'98), 1998. (Abstract)

 

Canonization for L^k-equivalence is hard.

In Computer Science Logic (CSL'97), 11th Workshop, 1997. Eds. M. Nielsen, W. Thomas. Lecture Notes in Computer Science 1414, Springer Verlag 1998.  (Abstract)

 

Existential least fixed-point logic and its relatives,

in Journal of Logic and Computation 7: 205-228, 1997. (Abstract)

 

Arity hierarchies,

in Annals of Pure and Applied Logic 82: 103-163, 1996. (Abstract)

 

Some remarks on finite Löwenheim-Skolem theorems,

in Mathematical Logic Quarterly 42: 569-571, 1996. (Abstract)

 

A double arity hierarchy theorem for transitive closure logic,

with Lauri Hella. In Archive for Mathematical Logic 35:157-171, 1996. (Abstract)

 

Complete Problems for fixed-point logics,

in Journal of Symbolic Logic 60: 517-527, 1995. (Abstract)

 

Bounded-arity hierarchies in fixed-point logics,

in Computer Science Logic (CSL'93), 7th Workshop, Swansea 1993. Eds. E. Börger,Y. Gurevich, K. Meinke. Lecture Notes in Computer Science 832, Springer Verlag. (Abstract)

The Complexity of Finite-Variable Theories

Habilitationsschrift at the Albert-Ludwigs-Universität Freiburg, November 1997.

 

The Structure of Fixed-Point Logics

Dissertation at the Albert-Ludwigs-Universität Freiburg, December 1994.

 

Fixpunktlogiken in der endlichen Modelltheorie

Diplomarbeit at the Albert-Ludwigs-Universität Freiburg, April 1992.