Martin Grohe

Eran Rosenbluth

CoRR, 2024

Future Directions in Foundations of Graph Machine Learning.

[BibT_eX]

[DOI]

CoRR, 2024

The Importance of Parameters in Database Queries.

[BibT_eX]

[DOI]

Proceedings of the 27th International Conference on Database Theory, 2024

2023

A Faster Isomorphism Test for Graphs of Small Degree.

[BibT_eX]

[DOI]

SIAM J. Comput., December, 2023

Physical pooling functions in graph neural networks for molecular property prediction.

[BibT_eX]

[DOI]

Artur M. Schweidtmann

Comput. Chem. Eng., April, 2023

Isomorphism Testing for Graphs Excluding Small Minors.

[BibT_eX]

[DOI]

Daniel Wiebking

SIAM J. Comput., February, 2023

Canonisation and Definability for Graphs of Bounded Rank Width.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., January, 2023

Isomorphism for Tournaments of Small Twin Width.

[BibT_eX]

[DOI]

CoRR, 2023

On the Parameterized Complexity of Learning Monadic Second-Order Formulas.

[BibT_eX]

[DOI]

Steffen van Bergerem

Nina Runde

CoRR, 2023

Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark.

[BibT_eX]

[DOI]

CoRR, 2023

Structural Node Embeddings with Homomorphism Counts.

[BibT_eX]

[DOI]

CoRR, 2023

The Iteration Number of the Weisfeiler-Leman Algorithm.

[BibT_eX]

[DOI]

Moritz Lichter

LICS, 2023

The Descriptive Complexity of Graph Neural Networks.

[BibT_eX]

[DOI]

LICS, 2023

Simulating Logspace-Recursion with Logarithmic Quantifier Depth.

[BibT_eX]

[DOI]

LICS, 2023

One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Some Might Say All You Need Is Sum.

[BibT_eX]

[DOI]

Eran Rosenbluth

Jan Tönshoff

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

WL meet VC.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Probabilistic Query Evaluation with Bag Semantics.

[BibT_eX]

[DOI]

Christoph Standke

Proceedings of the 26th International Conference on Database Theory, 2023

Stable Tuple Embeddings for Dynamic Databases.

[BibT_eX]

[DOI]

Proceedings of the 39th IEEE International Conference on Data Engineering, 2023

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Selecting Walk Schemes for Database Embedding.

[BibT_eX]

[DOI]

Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, 2023

2022

Infinite Probabilistic Databases.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2022

Independence in Infinite Probabilistic Databases.

[BibT_eX]

[DOI]

J. ACM, 2022

Generative Datalog with Continuous Distributions.

[BibT_eX]

[DOI]

Benjamin Lucien Kaminski

Joost-Pieter Katoen

J. ACM, 2022

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2022

Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2022

Graph Machine Learning for Design of High-Octane Fuels.

[BibT_eX]

[DOI]

Jan G. Rittig

Artur M. Schweidtmann

CoRR, 2022

Solving AC Power Flow with Graph Neural Networks under Realistic Constraints.

[BibT_eX]

[DOI]

CoRR, 2022

On the Parameterized Complexity of Learning First-Order Logic.

[BibT_eX]

[DOI]

Steffen van Bergerem

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Graph Similarity Based on Matrix Norms.

[BibT_eX]

[DOI]

Timo Gervens

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

Homomorphism Tensors and Linear Equations.

[BibT_eX]

[DOI]

Tim Seppelt

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Probabilistic Data with Continuous Distributions.

[BibT_eX]

[DOI]

Benjamin Lucien Kaminski

Joost-Pieter Katoen

SIGMOD Rec., 2021

Definable decompositions for graphs of bounded linear cliquewidth.

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Michal Pilipczuk

Log. Methods Comput. Sci., 2021

Weisfeiler and Leman go Machine Learning: The Story so far.

[BibT_eX]

[DOI]

CoRR, 2021

Dynamic Database Embeddings with FoRWaRD.

[BibT_eX]

[DOI]

CoRR, 2021

On the Parameterized Complexity of Learning Logic.

[BibT_eX]

[DOI]

Steffen van Bergerem

CoRR, 2021

Graph Learning with 1D Convolutions on Random Walks.

[BibT_eX]

[DOI]

CoRR, 2021

Isomorphism, canonization, and definability for graphs of bounded rank width.

[BibT_eX]

[DOI]

Commun. ACM, 2021

Deep Weisfeiler Leman.

[BibT_eX]

[DOI]

Daniel Wiebking

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Tuple-Independent Representations of Infinite Probabilistic Databases.

[BibT_eX]

[DOI]

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

The Effects of Randomness on the Stability of Node Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2021

A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

The Logic of Graph Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

The Surprising Power of Graph Neural Networks with Random Node Initialization.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021

Database Repairing with Soft Functional Dependencies.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Database Theory, 2021

Logarithmic Weisfeiler-Leman Identifies All Planar Graphs.

[BibT_eX]

[DOI]

Sandra Kiefer

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Recent advances on the graph isomorphism problem.

[BibT_eX]

[DOI]

Proceedings of the Surveys in Combinatorics, 2021

2020

An Improved Isomorphism Test for Bounded-tree-width Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Graph Neural Networks for Maximum Constraint Satisfaction.

[BibT_eX]

[DOI]

Frontiers Artif. Intell., 2020

Automorphism groups of graphs of bounded Hadwiger number.

[BibT_eX]

[DOI]

Daniel Wiebking

CoRR, 2020

Standard Probabilistic Databases.

[BibT_eX]

[DOI]

CoRR, 2020

The Effects of Randomness on the Stability of Node Embeddings.

[BibT_eX]

[DOI]

CoRR, 2020

The graph isomorphism problem.

[BibT_eX]

[DOI]

Commun. ACM, 2020

Weisfeiler and Leman's Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data.

[BibT_eX]

[DOI]

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Counting Bounded Tree Depth Homomorphisms.

[BibT_eX]

[DOI]

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

2019

A Finite-Model-Theoretic View on Propositional Proof Complexity.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2019

RUN-CSP: Unsupervised Learning of Message Passing Networks for Binary Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

CoRR, 2019

Probabilistic Databases with an Infinite Open-World Assumption.

[BibT_eX]

[DOI]

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

The Complexity of Homomorphism Indistinguishability.

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus.

[BibT_eX]

[DOI]

Sandra Kiefer

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Symmetry and Similarity (Invited Talk).

[BibT_eX]

[DOI]

Konstantinos S. Stavropoulos

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Coloring and Covering Nowhere Dense Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231).

[BibT_eX]

[DOI]

Venkatesan Guruswami

Stanislav Zivný

Dagstuhl Reports, 2018

Weisfeiler-Leman meets Homomorphisms.

[BibT_eX]

[DOI]

Holger Dell

CoRR, 2018

Towards faster isomorphism tests for bounded-degree graphs.

[BibT_eX]

[DOI]

CoRR, 2018

First-Order Query Evaluation with Cardinality Conditions.

[BibT_eX]

[DOI]

Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Graph Similarity and Approximate Isomorphism.

[BibT_eX]

[DOI]

Gerhard J. Woeginger

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Lovász Meets Weisfeiler and Leman.

[BibT_eX]

[DOI]

Holger Dell

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement.

[BibT_eX]

[DOI]

Christoph Berkholz

Paul S. Bonsma

Theory Comput. Syst., 2017

Deciding First-Order Properties of Nowhere Dense Graphs.

[BibT_eX]

[DOI]

Sebastian Siebertz

J. ACM, 2017

Learning MSO-definable hypotheses on string.

[BibT_eX]

[DOI]

Christof Löding

CoRR, 2017

The Hardness of Embedding Grids and Walls.

[BibT_eX]

[DOI]

Bingkai Lin

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism.

[BibT_eX]

[DOI]

Christoph Berkholz

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Learning first-order definable concepts over structures of small degree.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Descriptive complexity of linear equation systems and applications to propositional proof complexity.

[BibT_eX]

[DOI]

Wied Pakusa

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Learning MSO-definable hypotheses on strings.

[BibT_eX]

[DOI]

Christof Löding

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

Descriptive Complexity, Canonisation, and Definable Graph Structure Theory

[BibT_eX]

[DOI]

Lecture Notes in Logic 47, Cambridge University Press, ISBN: 9781139028868, 2017

2016

Where First-Order and Monadic Second-Order Logic Coincide.

[BibT_eX]

[DOI]

Michael Elberfeld

Till Tantau

ACM Trans. Comput. Log., 2016

Computing with Tangles.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles).

[BibT_eX]

[DOI]

CoRR, 2016

Order Invariance on Decomposable Structures.

[BibT_eX]

[DOI]

Michael Elberfeld

Marlin Frickenschmidt

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Tangles and Connectivity in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2016

Quasi-4-Connected Components.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Pebble Games and linear equations.

[BibT_eX]

[DOI]

Konstantinos S. Stavropoulos

Martin Otto

J. Symb. Log., 2015

Theory and Practice of SAT Solving (Dagstuhl Seminar 15171).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

Colouring and Covering Nowhere Dense Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Limitations of Algebraic Approaches to Graph Isomorphism Testing.

[BibT_eX]

[DOI]

Christoph Berkholz

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Isomorphism Testing for Graphs of Bounded Rank Width.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Is Polynomial Time Choiceless?

[BibT_eX]

[DOI]

Erich Grädel

Proceedings of the Fields of Logic and Computation II, 2015

2014

Constraint Solving via Fractional Edge Covers.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

Database Theory Column Report on PODS 2014.

[BibT_eX]

[DOI]

SIGACT News, 2014

Choiceless Polynomial Time on Structures with Small Abelian Colour Classes.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Dimension Reduction via Colour Refinement.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

Algorithmic Meta Theorems for Sparse Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2014

Monadic Datalog Containment on Trees.

[BibT_eX]

[DOI]

André Frochaux

Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management, 2014

Power Iterated Color Refinement.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013

Size Bounds and Query Plans for Relational Joins.

[BibT_eX]

[DOI]

Albert Atserias

SIAM J. Comput., 2013

A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory.

[BibT_eX]

[DOI]

Ken-ichi Kawarabayashi

Bruce A. Reed

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Logical and Structural Approaches to the Graph Isomorphism Problem.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Characterisations of Nowhere Dense Graphs (Invited Talk).

[BibT_eX]

[DOI]

Sebastian Siebertz

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Bounds and Algorithms for Joins via Fractional Edge Covers.

[BibT_eX]

[DOI]

Proceedings of the In Search of Elegance in the Theory and Practice of Computation, 2013

2012

Enumerating homomorphisms.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

Fixed-point definability and polynomial time on graphs with excluded minors.

[BibT_eX]

[DOI]

J. ACM, 2012

L-Recursion and a new Logic for Logarithmic Space

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2012

Structural and logical approaches to the graph isomorphism problem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Computational Complexity of Discrete Problems (Dagstuhl Seminar 11121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2011

From polynomial time queries to graph structure theory.

[BibT_eX]

[DOI]

Commun. ACM, 2011

Finding topological subgraphs is fixed-parameter tractable.

[BibT_eX]

[DOI]

Ken-ichi Kawarabayashi

Paul Wollan

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

A Complexity Dichotomy for Partition Functions with Mixed Signs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Constraint satisfaction with succinctly specified relations.

[BibT_eX]

[DOI]

Hubie Chen

J. Comput. Syst. Sci., 2010

Randomisation and Derandomisation in Descriptive Complexity Theory.

[BibT_eX]

[DOI]

Kord Eickmeyer

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation, 2010

2009

Database Query Processing Using Finite Cursor Machines.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2009

On tree width, bramble size, and expansion.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2009

Lower bounds for processing data with few random accesses to external memory.

[BibT_eX]

[DOI]

André Hernich

J. ACM, 2009

The Complexity of Datalog on Linear Orders

[BibT_eX]

[DOI]

Götz Schwandtner

Log. Methods Comput. Sci., 2009

Logics with Rank Operators.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability.

[BibT_eX]

[DOI]

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability.

[BibT_eX]

[DOI]

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

Fixed-Point Definability and Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

Counting Homomorphisms and Partition Functions.

[BibT_eX]

Marc Thurley

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

Methods for Algorithmic Meta Theorems.

[BibT_eX]

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008

Preservation under Extensions on Well-Behaved Finite Structures.

[BibT_eX]

[DOI]

Albert Atserias

Anuj Dawar

SIAM J. Comput., 2008

Algorithmic Meta Theorems.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Computing excluded minors.

[BibT_eX]

[DOI]

Isolde Adler

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Definable Tree Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, 2008

The Quest for a Logic Capturing PTIME.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, 2008

Non-dichotomies in Constraint Satisfaction Complexity.

[BibT_eX]

[DOI]

Manuel Bodirsky

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Approximation of Natural W[P]-Complete Minimisation Problems Is Hard.

[BibT_eX]

[DOI]

Kord Eickmeyer

Magdalena Grüber

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Tight lower bounds for query processing on streaming and external memory data.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

An analysis of the W*-hierarchy.

[BibT_eX]

[DOI]

J. Symb. Log., 2007

The complexity of homomorphism and constraint satisfaction problems seen from the other side.

[BibT_eX]

[DOI]

J. ACM, 2007

Hypertree width and related hypergraph invariants.

[BibT_eX]

[DOI]

Isolde Adler

Georg Gottlob

Eur. J. Comb., 2007

Logic, Graphs, and Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

On Parameterized Approximability.

[BibT_eX]

[DOI]

Magdalena Grüber

Electron. Colloquium Comput. Complex., 2007

Bounded fixed-parameter tractability and reducibility.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2007

Locally Excluding a Minor.

[BibT_eX]

[DOI]

Anuj Dawar

Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Parameterized Approximability of the Disjoint Cycle Problem.

[BibT_eX]

[DOI]

Magdalena Grüber

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Model Theory Makes Formulas Large.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

The Ackermann Award 2007.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006

Parameterized Complexity Theory

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-29953-0, 2006

Bounded fixed-parameter tractability and log2n nondeterministic bits.

[BibT_eX]

[DOI]

Mark Weyer

J. Comput. Syst. Sci., 2006

An Isomorphism between Subexponential and Parameterized Complexity Theory

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Randomized computations on large data sets: tight lower bounds.

[BibT_eX]

[DOI]

André Hernich

Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

The Structure of Tractable Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Approximation Schemes for First-Order Definable Optimisation Problems.

[BibT_eX]

[DOI]

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Testing Graph Isomorphism in Parallel by Playing a Game.

[BibT_eX]

[DOI]

Oleg Verbitsky

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Machine-based methods in parameterized complexity theory.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

The complexity of partition functions.

[BibT_eX]

[DOI]

Andrei A. Bulatov

Theor. Comput. Sci., 2005

The succinctness of first-order logic on linear orders.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2005

Model-checking problems as a basis for parameterized intractability.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2005

Hypertree Decompositions: Structure, Algorithms, and Applications.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

Lower bounds for sorting with few random accesses to external memory.

[BibT_eX]

[DOI]

Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

The Expressive Power of Two-Variable Least Fixed-Point Logics.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

The Complexity of Querying External Memory and Streaming Data.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability.

[BibT_eX]

[DOI]

Rodney G. Downey

Gerhard J. Woeginger

Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005

05301 Summary - Exact Algorithms and Fixed-Parameter Tractability.

[BibT_eX]

[DOI]

Rodney G. Downey

Gerhard J. Woeginger

Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005

2004

The Parameterized Complexity of Counting Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Learnability and Definability in Trees and Similar Structures.

[BibT_eX]

[DOI]

György Turán

Theory Comput. Syst., 2004

Computing crossing numbers in quadratic time.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Comparing the succinctness of monadic query languages over finite trees.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2004

Parametrized Complexity and Subexponential Time (Column: Computational Complexity).

[BibT_eX]

Bull. EATCS, 2004

An existential locality theorem.

[BibT_eX]

[DOI]

Stefan Wöhrle

Ann. Pure Appl. Log., 2004

The complexity of first-order and monadic second-order logic revisited.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2004

Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits.

[BibT_eX]

[DOI]

Mark Weyer

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Reachability and connectivity queries in constraint databases.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

Describing parameterized complexity classes.

[BibT_eX]

[DOI]

Inf. Comput., 2003

Local Tree-Width, Excluded Minors, and Approximation Algorithms.

[BibT_eX]

[DOI]

Comb., 2003

Path Queries on Compressed XML.

[BibT_eX]

[DOI]

Peter Buneman

Proceedings of 29th International Conference on Very Large Data Bases, 2003

Query Evaluation on Compressed Trees (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

Monadic Datalog on Trees (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the FICS '03, 2003

Bounded Nondeterminism and Alternation in Parameterized Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

On first-order topological queries.

[BibT_eX]

[DOI]

Luc Segoufin

ACM Trans. Comput. Log., 2002

Parameterized Complexity for the Database Theorist.

[BibT_eX]

[DOI]

SIGMOD Rec., 2002

Query evaluation via tree-decompositions.

[BibT_eX]

[DOI]

J. ACM, 2002

Large Finite Structures with Few Lk-Types.

[BibT_eX]

[DOI]

Inf. Comput., 2002

2001

Fixed-Parameter Tractability, Definability, and Model-Checking.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

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

[BibT_eX]

[DOI]

J. ACM, 2001

When is the evaluation of conjunctive queries tractable?

[BibT_eX]

[DOI]

Thomas Schwentick

Luc Segoufin

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Generalized Model-Checking Problems for First-Order Logic.

[BibT_eX]

[DOI]

Proceedings of the STACS 2001, 2001

The Parameterized Complexity of Database Queries.

[BibT_eX]

[DOI]

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

2000

Locality of order-invariant first-order formulas.

[BibT_eX]

[DOI]

Thomas Schwentick

ACM Trans. Comput. Log., 2000

On Fixed-Point Logic With Counting.

[BibT_eX]

[DOI]

J. Symb. Log., 2000

Isomorphism testing for embeddable graphs through definability.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Equivalence in Finite-Variable Logics is Complete for Polynomial Time.

[BibT_eX]

[DOI]

Comb., 1999

Definability and Descriptive Complexity on Databases of Bounded Tree-Width.

[BibT_eX]

[DOI]

Julian Mariño

Proceedings of the Database Theory, 1999

Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

Descriptive and Parameterized Complexity.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 13th International Workshop, 1999

1998

Finite variable logics in descriptive complexity theory.

[BibT_eX]

[DOI]

Bull. Symb. Log., 1998

Fixed-Point Logics on Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1997

Existential Least Fixed-Point Logic and its Relatives.

[BibT_eX]

[DOI]

J. Log. Comput., 1997

Large Finite Structures with Few Lk-Types.

[BibT_eX]

[DOI]

Proceedings of the Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29, 1997

Canonization for Lk-equivalence is Hard.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996

Some Remarks on Finite Löwenheim-Skolem Theorems.

[BibT_eX]

[DOI]

Math. Log. Q., 1996

Arity Hierarchies.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 1996

A double arity hierarchy theorem for transitive closure logic.

[BibT_eX]

[DOI]

Lauri Hella

Arch. Math. Log., 1996

1995

Complete Problems for Fixed-Point Logics.

[BibT_eX]

[DOI]

J. Symb. Log., 1995

1993

Bounded-Arity Hierarchies in Fixed-Point Logics.

[BibT_eX]

[DOI]