| Publication | Date of Publication | Type |
|---|
| The parameterized complexity of learning monadic second-order logic | 2026-06-09 | Paper |
| The parameterized complexity of counting problems | 2026-05-29 | Paper |
| The complexity of homomorphism and constraint satisfaction problems seen from the other side | 2026-05-29 | Paper |
| Logarithmic Weisfeiler-Leman identifies all planar graphs | 2026-05-12 | Paper |
| Database repairing with soft functional dependencies | 2026-04-16 | Paper |
Isomorphism for tournaments of small twin width
TheoretiCS | 2026-03-23 | Paper |
| The descriptive complexity of graph neural networks | 2026-02-27 | Paper |
| Simulating logspace-recursion with logarithmic quantifier depth | 2026-02-27 | Paper |
| The iteration number of the Weisfeiler-Leman algorithm | 2026-02-27 | Paper |
| Isomorphism for tournaments of small twin width | 2026-01-14 | Paper |
| The importance of parameters in database queries | 2025-11-11 | Paper |
Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
Journal of the ACM | 2025-08-21 | Paper |
| Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements | 2025-08-15 | Paper |
| Isomorphism testing for graphs excluding small minors | 2025-08-12 | Paper |
| A faster isomorphism test for graphs of small degree | 2025-08-12 | Paper |
| Isomorphism testing for graphs of bounded rank width | 2025-08-05 | Paper |
| Are targeted messages more effective? | 2025-06-18 | Paper |
Homomorphism tensors and linear equations
Advances in Combinatorics | 2025-05-21 | Paper |
The iteration number of the Weisfeiler-Leman algorithm
ACM Transactions on Computational Logic | 2025-02-14 | Paper |
The descriptive complexity of graph neural networks
TheoretiCS | 2025-01-29 | Paper |
| Canonisation and definability for graphs of bounded rank width | 2024-12-19 | Paper |
| Probabilistic query evaluation with bag semantics | 2024-10-08 | Paper |
| Graph similarity based on matrix norms | 2024-08-06 | Paper |
| Homomorphism tensors and linear equations | 2024-06-24 | Paper |
Generative Datalog with continuous distributions
Journal of the ACM | 2024-06-06 | Paper |
Database repairing with soft functional dependencies
ACM Transactions on Database Systems | 2024-04-30 | Paper |
scientific article; zbMATH DE number 7788492 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
A Faster Isomorphism Test for Graphs of Small Degree
SIAM Journal on Computing | 2023-12-19 | Paper |
| A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk) | 2023-08-08 | Paper |
Independence in Infinite Probabilistic Databases
Journal of the ACM | 2023-04-27 | Paper |
| Simulating Logspace-Recursion with Logarithmic Quantifier Depth | 2023-04-25 | Paper |
Isomorphism Testing for Graphs Excluding Small Minors
SIAM Journal on Computing | 2023-04-04 | Paper |
Infinite Probabilistic Databases
(available as arXiv preprint) | 2023-02-07 | Paper |
| Weisfeiler and Leman's Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk). | 2023-02-07 | Paper |
Canonisation and Definability for Graphs of Bounded Rank Width
ACM Transactions on Computational Logic | 2023-02-07 | Paper |
Recent advances on the graph isomorphism problem
(available as arXiv preprint) | 2022-11-18 | Paper |
| Recent advances on the graph isomorphism problem | 2022-11-18 | Paper |
scientific article; zbMATH DE number 7566047 (Why is no real title available?)
(available as arXiv preprint) | 2022-08-02 | Paper |
| scientific article; zbMATH DE number 7566047 (Why is no real title available?) | 2022-08-02 | Paper |
| The Complexity of Homomorphism Indistinguishability | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561610 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
| Symmetry and Similarity (Invited Talk) | 2022-07-21 | Paper |
| Graph Similarity Based on Matrix Norms | 2022-06-30 | Paper |
Graph similarity and approximate isomorphism
(available as arXiv preprint) | 2021-08-04 | Paper |
An improved isomorphism test for bounded-tree-width graphs
(available as arXiv preprint) | 2021-07-28 | Paper |
Lov\'asz Meets Weisfeiler and Leman
(available as arXiv preprint) | 2021-07-28 | Paper |
| Logarithmic Weisfeiler-Leman Identifies All Planar Graphs | 2021-06-30 | Paper |
An improved isomorphism test for bounded-tree-width graphs
ACM Transactions on Algorithms | 2021-05-03 | Paper |
Definable decompositions for graphs of bounded linear cliquewidth
(available as arXiv preprint) | 2021-03-26 | Paper |
| Definable decompositions for graphs of bounded linear cliquewidth | 2021-03-26 | Paper |
Counting bounded tree depth homomorphisms
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science | 2021-01-21 | Paper |
Definable decompositions for graphs of bounded linear cliquewidth
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science | 2021-01-20 | Paper |
| Learning first-order definable concepts over structures of small degree | 2021-01-19 | Paper |
Learning first-order definable concepts over structures of small degree
(available as arXiv preprint) | 2021-01-19 | Paper |
| Descriptive complexity of linear equation systems and applications to propositional proof complexity | 2021-01-19 | Paper |
| Automorphism groups of graphs of bounded Hadwiger number | 2020-12-28 | Paper |
A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
(available as arXiv preprint) | 2019-04-15 | Paper |
A finite-model-theoretic view on propositional proof complexity
(available as arXiv preprint) | 2019-02-25 | Paper |
| scientific article; zbMATH DE number 6999908 (Why is no real title available?) | 2019-01-10 | Paper |
scientific article; zbMATH DE number 6999908 (Why is no real title available?)
(available as arXiv preprint) | 2019-01-10 | Paper |
Coloring and covering nowhere dense graphs
SIAM Journal on Discrete Mathematics | 2018-10-31 | Paper |
Constraint solving via fractional edge covers
ACM Transactions on Algorithms | 2018-10-30 | Paper |
| Bounds and algorithms for joins via fractional edge covers | 2018-10-18 | Paper |
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Deciding first-order properties of nowhere dense graphs
Journal of the ACM | 2018-05-17 | Paper |
Order invariance on decomposable structures
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science | 2018-04-23 | Paper |
The hardness of embedding grids and walls
(available as arXiv preprint) | 2018-01-04 | Paper |
Quasi-4-Connected Components
(available as arXiv preprint) | 2017-12-19 | Paper |
Tight lower and upper bounds for the complexity of canonical colour refinement
Theory of Computing Systems | 2017-08-15 | Paper |
Where first-order and monadic second-order logic coincide
ACM Transactions on Computational Logic | 2017-07-13 | Paper |
Locality of order-invariant first-order formulas
ACM Transactions on Computational Logic | 2017-06-13 | Paper |
On first-order topological queries
ACM Transactions on Computational Logic | 2017-06-13 | Paper |
| Descriptive Complexity, Canonisation, and Definable Graph Structure Theory | 2017-05-22 | Paper |
Where first-order and monadic second-order logic coincide
2012 27th Annual IEEE Symposium on Logic in Computer Science | 2017-05-16 | Paper |
| Characterisations of nowhere dense graphs (invited talk) | 2017-02-21 | Paper |
Colouring and covering nowhere dense graphs
Graph-Theoretic Concepts in Computer Science | 2016-10-21 | Paper |
Computing with tangles
SIAM Journal on Discrete Mathematics | 2016-06-23 | Paper |
| Tangled up in Blue (A Survey on Connectivity, Decompositions, and Tangles) | 2016-05-21 | Paper |
Tangles and connectivity in graphs
Language and Automata Theory and Applications | 2016-04-13 | Paper |
Query evaluation via tree-decompositions
Journal of the ACM | 2015-12-07 | Paper |
Lower bounds for processing data with few random accesses to external memory
Journal of the ACM | 2015-11-11 | Paper |
PEBBLE GAMES AND LINEAR EQUATIONS
Journal of Symbolic Logic | 2015-11-09 | Paper |
PEBBLE GAMES AND LINEAR EQUATIONS
Journal of Symbolic Logic | 2015-11-09 | Paper |
Deciding first-order properties of locally tree-decomposable structures
Journal of the ACM | 2015-10-30 | Paper |
Limitations of algebraic approaches to graph isomorphism testing
Automata, Languages, and Programming | 2015-10-27 | Paper |
Is polynomial time choiceless?
Fields of Logic and Computation II | 2015-09-22 | Paper |
Computing with Tangles
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Deciding first-order properties of nowhere dense graphs
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
SIAM Journal on Computing | 2015-06-02 | Paper |
| Isomorphism Testing for Graphs of Bounded Rank Width | 2015-05-14 | Paper |
When is the evaluation of conjunctive queries tractable?
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Computing crossing numbers in quadratic time
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Choiceless polynomial time on structures with small abelian colour classes
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Dimension reduction via colour refinement
Algorithms - ESA 2014 | 2014-10-08 | Paper |
Isomorphism testing for embeddable graphs through definability
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Algorithmic meta theorems for sparse graph classes
Computer Science - Theory and Applications | 2014-06-24 | Paper |
Finding topological subgraphs is fixed-parameter tractable
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Finding topological subgraphs is fixed-parameter tractable
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Fixed-point definability and polynomial time on graphs with excluded minors
Journal of the ACM | 2014-02-17 | Paper |
Size bounds and query plans for relational joins
SIAM Journal on Computing | 2013-11-14 | Paper |
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Lecture Notes in Computer Science | 2013-09-17 | Paper |
L-recursion and a new logic for logarithmic space
Logical Methods in Computer Science | 2013-04-09 | Paper |
| Pebble games and linear equations | 2012-11-22 | Paper |
| L-recursion and a new logic for logarithmic space | 2012-09-18 | Paper |
L-recursion and a new logic for logarithmic space
(available as arXiv preprint) | 2012-09-18 | Paper |
Enumerating homomorphisms
Journal of Computer and System Sciences | 2012-05-11 | Paper |
| A complexity dichotomy for partition functions with mixed signs | 2012-04-24 | Paper |
| Enumerating homomorphisms | 2012-04-24 | Paper |
Randomisation and derandomisation in descriptive complexity theory
Logical Methods in Computer Science | 2012-04-02 | Paper |
| Methods for algorithmic meta theorems | 2012-03-02 | Paper |
| Counting homomorphisms and partition functions | 2012-03-02 | Paper |
A Complexity Dichotomy for Partition Functions with Mixed Signs
SIAM Journal on Computing | 2011-04-04 | Paper |
| Logic, graphs, and algorithms | 2011-03-30 | Paper |
Constraint satisfaction with succinctly specified relations
Journal of Computer and System Sciences | 2010-10-07 | Paper |
Randomisation and derandomisation in descriptive complexity theory
Computer Science Logic | 2010-09-03 | Paper |
Fixed-point definability and polynomial time on chordal graphs and line graphs
Fields of Logic and Computation | 2010-09-03 | Paper |
Constraint solving via fractional edge covers
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
| scientific article; zbMATH DE number 5764786 (Why is no real title available?) | 2010-08-06 | Paper |
| Hypertree-width and related hypergraph invariants | 2010-07-30 | Paper |
Fixed-Point Definability and Polynomial Time
Computer Science Logic | 2009-11-12 | Paper |
| scientific article; zbMATH DE number 5604125 (Why is no real title available?) | 2009-09-15 | Paper |
Preservation under Extensions on Well-Behaved Finite Structures
SIAM Journal on Computing | 2009-08-20 | Paper |
Database query processing using finite cursor machines
Theory of Computing Systems | 2009-08-06 | Paper |
The Complexity of Datalog on Linear Orders
Logical Methods in Computer Science | 2009-04-29 | Paper |
Testing Graph Isomorphism in Parallel by Playing a Game
Automata, Languages and Programming | 2009-03-12 | Paper |
The Ackermann Award 2007
Computer Science Logic | 2009-03-05 | Paper |
On tree width, bramble size, and expansion
Journal of Combinatorial Theory. Series B | 2009-01-21 | Paper |
The complexity of homomorphism and constraint satisfaction problems seen from the other side
Journal of the ACM | 2008-12-21 | Paper |
Non-dichotomies in Constraint Satisfaction Complexity
Automata, Languages and Programming | 2008-08-19 | Paper |
An Isomorphism Between Subexponential and Parameterized Complexity Theory
SIAM Journal on Computing | 2008-08-14 | Paper |
On Parameterized Approximability
Parameterized and Exact Computation | 2008-06-03 | Paper |
Model Theory Makes Formulas Large
Automata, Languages and Programming | 2007-11-28 | Paper |
Parameterized Approximability of the Disjoint Cycle Problem
Automata, Languages and Programming | 2007-11-28 | Paper |
Hypertree width and related hypergraph invariants
European Journal of Combinatorics | 2007-11-21 | Paper |
The succinctness of first-order logic on linear orders
Logical Methods in Computer Science | 2007-10-11 | Paper |
Model-Checking Problems as a Basis for Parameterized Intractability
Logical Methods in Computer Science | 2007-10-11 | Paper |
Bounded fixed-parameter tractability and reducibility
Annals of Pure and Applied Logic | 2007-09-28 | Paper |
The Structure of Tractable Constraint Satisfaction Problems
Lecture Notes in Computer Science | 2007-09-05 | Paper |
Tight lower bounds for query processing on streaming and external memory data
Theoretical Computer Science | 2007-07-16 | Paper |
An analysis of the W*-hierarchy
Journal of Symbolic Logic | 2007-07-09 | Paper |
Computer Science Logic
Lecture Notes in Computer Science | 2007-06-21 | Paper |
Graph-Theoretic Concepts in Computer Science
Lecture Notes in Computer Science | 2006-11-01 | Paper |
Fundamentals of Computation Theory
Lecture Notes in Computer Science | 2006-10-20 | Paper |
Mathematical Foundations of Computer Science 2005
Lecture Notes in Computer Science | 2006-10-20 | Paper |
Large finite structures with few \(L^k\)-types
Information and Computation | 2006-10-10 | Paper |
Local tree-width, excluded minors, and approximation algorithms
Combinatorica | 2006-06-27 | Paper |
Parametrized complexity theory.
Texts in Theoretical Computer Science. An EATCS Series | 2006-05-24 | Paper |
Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
Journal of Computer and System Sciences | 2006-01-10 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
The complexity of partition functions
Theoretical Computer Science | 2006-01-09 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Machine-based methods in parameterized complexity theory
Theoretical Computer Science | 2005-06-30 | Paper |
Comparing the succinctness of monadic query languages over finite trees
RAIRO - Theoretical Informatics and Applications | 2005-03-21 | Paper |
Comparing the succinctness of monadic query languages over finite trees
RAIRO - Theoretical Informatics and Applications | 2005-03-21 | Paper |
Comparing the succinctness of monadic query languages over finite trees
RAIRO - Theoretical Informatics and Applications | 2005-03-21 | Paper |
The Parameterized Complexity of Counting Problems
SIAM Journal on Computing | 2005-02-21 | Paper |
Learnability and definability in trees and similar structures
Theory of Computing Systems | 2005-01-25 | Paper |
An existential locality theorem
Annals of Pure and Applied Logic | 2004-11-22 | Paper |
Computing crossing numbers in quadratic time
Journal of Computer and System Sciences | 2004-11-22 | Paper |
The complexity of first-order and monadic second-order logic revisited
Annals of Pure and Applied Logic | 2004-11-18 | Paper |
Describing parameterized complexity classes
Information and Computation | 2004-08-19 | Paper |
| scientific article; zbMATH DE number 2086399 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2086423 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2080462 (Why is no real title available?) | 2004-08-04 | Paper |
Reachability and connectivity queries in constraint databases
Journal of Computer and System Sciences | 2003-06-25 | Paper |
| scientific article; zbMATH DE number 1841816 (Why is no real title available?) | 2002-12-04 | Paper |
| scientific article; zbMATH DE number 1688350 (Why is no real title available?) | 2002-01-09 | Paper |
Fixed-parameter tractability, definability, and model-checking
SIAM Journal on Computing | 2001-06-21 | Paper |
| scientific article; zbMATH DE number 1555183 (Why is no real title available?) | 2001-01-22 | Paper |
On fixed-point logic with counting
Journal of Symbolic Logic | 2001-01-14 | Paper |
Equivalence in finite-variable logics is complete for polynomial time
Combinatorica | 2000-05-14 | Paper |
| scientific article; zbMATH DE number 1424025 (Why is no real title available?) | 2000-03-23 | Paper |
| scientific article; zbMATH DE number 1405654 (Why is no real title available?) | 2000-02-23 | Paper |
| scientific article; zbMATH DE number 1392292 (Why is no real title available?) | 2000-01-24 | Paper |
Finite Variable Logics in Descriptive Complexity Theory
The Bulletin of Symbolic Logic | 1999-06-29 | Paper |
Finite Variable Logics in Descriptive Complexity Theory
The Bulletin of Symbolic Logic | 1999-06-29 | Paper |
| scientific article; zbMATH DE number 1223623 (Why is no real title available?) | 1999-06-07 | Paper |
| scientific article; zbMATH DE number 1222579 (Why is no real title available?) | 1998-11-11 | Paper |
Existential least fixed-point logic and its relatives
Journal Of Logic And Computation | 1997-06-10 | Paper |
Arity hierarchies
Annals of Pure and Applied Logic | 1997-04-21 | Paper |
Some Remarks on Finite Löwenheim‐Skolem Theorems
Mathematical Logic Quarterly | 1997-03-19 | Paper |
A double arity hierarchy theorem for transitive closure logic
Archive for Mathematical Logic | 1996-08-22 | Paper |
| scientific article; zbMATH DE number 850318 (Why is no real title available?) | 1996-03-04 | Paper |
Complete problems for fixed-point logics
Journal of Symbolic Logic | 1995-11-28 | Paper |
Homomorphism Tensors and Linear Equations
(available as arXiv preprint) | N/A | Paper |
