| Publication | Date of Publication | Type |
|---|
| Canonization of a random graph by two matrix-vector multiplications | 2025-01-06 | Paper |
On isomorphism-invariant antistochastic properties of random graphs
SIAM Journal on Discrete Mathematics | 2024-12-18 | Paper |
| Canonization of a random circulant graph by counting walks | 2024-07-19 | Paper |
The Complexity of Drawing Graphs on Few Lines and Few Planes
Journal of Graph Algorithms and Applications | 2023-09-20 | Paper |
On anti-stochastic properties of unlabeled graphs
Graph-Theoretic Concepts in Computer Science | 2023-05-05 | Paper |
The Weisfeiler-Leman algorithm and recognition of graph properties
Lecture Notes in Computer Science | 2023-03-22 | Paper |
| Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm | 2023-02-07 | Paper |
On the Weisfeiler-Leman dimension of fractional packing
Information and Computation | 2022-10-13 | Paper |
The Weisfeiler-Leman algorithm and recognition of graph properties
Theoretical Computer Science | 2021-11-18 | Paper |
Local WL invariance and hidden shades of regularity
Discrete Applied Mathematics | 2021-10-21 | Paper |
Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
SIAM Journal on Discrete Mathematics | 2021-08-20 | Paper |
| Drawing graphs on few lines and few planes | 2020-11-12 | Paper |
On the Weisfeiler-Leman dimension of fractional packing
Language and Automata Theory and Applications | 2020-07-27 | Paper |
On Weisfeiler-Leman invariance: subgraph counts and related graph properties
Journal of Computer and System Sciences | 2020-06-09 | Paper |
On the first-order complexity of induced subgraph isomorphism
(available as arXiv preprint) | 2020-05-26 | Paper |
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
(available as arXiv preprint) | 2020-05-18 | Paper |
On Weisfeiler-Leman invariance: subgraph counts and related graph properties
Fundamentals of Computation Theory | 2020-01-30 | Paper |
Tight bounds on the asymptotic descriptive complexity of subgraph isomorphism
ACM Transactions on Computational Logic | 2019-07-04 | Paper |
The descriptive complexity of subgraph isomorphism without numerics
Theory of Computing Systems | 2019-07-04 | Paper |
On the first-order complexity of induced subgraph isomorphism
(available as arXiv preprint) | 2019-03-18 | Paper |
| Around and beyond the isomorphism problem for interval graphs | 2018-09-04 | Paper |
Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth
2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science | 2018-04-23 | Paper |
Graph isomorphism, color refinement, and compactness
Computational Complexity | 2017-10-18 | Paper |
On the speed of constraint propagation and the time complexity of arc consistency testing
Journal of Computer and System Sciences | 2017-10-11 | Paper |
The complexity of drawing graphs on few lines and few planes
(available as arXiv preprint) | 2017-09-22 | Paper |
The descriptive complexity of subgraph isomorphism without numerics
Lecture Notes in Computer Science | 2017-08-22 | Paper |
Circular-arc hypergraphs: rigidity via connectedness
Discrete Applied Mathematics | 2017-03-15 | Paper |
Drawing Graphs on Few Lines and Few Planes
Lecture Notes in Computer Science | 2017-02-21 | Paper |
Drawing Graphs on Few Lines and Few Planes
Lecture Notes in Computer Science | 2017-02-21 | Paper |
| Bounds for the quantifier depth in finite-variable logics: alternation hierarchy | 2017-02-02 | Paper |
| Solving the canonical representation and star system problems for proper circular-arc graphs in logspace | 2017-01-26 | Paper |
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
Journal of Discrete Algorithms | 2016-12-09 | Paper |
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
Journal of Discrete Algorithms | 2016-12-09 | Paper |
On the isomorphism problem for Helly circular-arc graphs
Information and Computation | 2016-03-10 | Paper |
On the power of color refinement
Fundamentals of Computation Theory | 2015-09-29 | Paper |
Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
ACM Transactions on Computational Logic | 2015-09-17 | Paper |
On Tinhofer's linear programming approach to isomorphism testing
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM
International Journal of Foundations of Computer Science | 2015-04-30 | Paper |
Helly circular-arc graph isomorphism is in logspace
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
On the speed of constraint propagation and the time complexity of arc consistency testing
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
Logical complexity of graphs: a survey
(available as arXiv preprint) | 2012-03-02 | Paper |
Interval graphs: canonical representations in logspace
SIAM Journal on Computing | 2012-02-11 | Paper |
On collinear sets in straight-line drawings
Graph-Theoretic Concepts in Computer Science | 2011-12-16 | Paper |
Untangling planar graphs from a specified vertex position-Hard cases
Discrete Applied Mathematics | 2011-05-17 | Paper |
Fermat's spiral and the line between Yin and Yang
The American Mathematical Monthly | 2010-12-14 | Paper |
Interval graphs: canonical representation in logspace
Automata, Languages and Programming | 2010-09-07 | Paper |
Decomposable graphs and definitions with no quantifier alternation
(available as arXiv preprint) | 2010-07-30 | Paper |
| Decomposable graphs and definitions with no quantifier alternation | 2010-07-30 | Paper |
Testing Graph Isomorphism in Parallel by Playing a Game
Automata, Languages and Programming | 2009-03-12 | Paper |
| scientific article; zbMATH DE number 5520320 (Why is no real title available?) | 2009-02-28 | Paper |
From Invariants to Canonization in Parallel
Computer Science – Theory and Applications | 2008-06-05 | Paper |
On the obfuscation complexity of planar graphs
Theoretical Computer Science | 2008-05-28 | Paper |
On the Computational Complexity of the Forcing Chromatic Number
SIAM Journal on Computing | 2008-03-28 | Paper |
Decomposable graphs and definitions with no quantifier alternation
European Journal of Combinatorics | 2007-11-21 | Paper |
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
STACS 2007 | 2007-09-03 | Paper |
| How Much Work Does It Take To Straighten a Plane Graph Out? | 2007-07-23 | Paper |
First-Order Definability of Trees and Sparse Random Graphs
Combinatorics, Probability and Computing | 2007-05-15 | Paper |
The first order definability of graphs: Upper bounds for quantifier depth
Discrete Applied Mathematics | 2007-01-09 | Paper |
| scientific article; zbMATH DE number 5055051 (Why is no real title available?) | 2006-09-19 | Paper |
| On the logical complexity of convex polygon dissections | 2006-07-21 | Paper |
Succinct definitions in the first order theory of graphs
Annals of Pure and Applied Logic | 2006-04-28 | Paper |
Descriptive complexity of finite structures: Saving the quantifier rank
Journal of Symbolic Logic | 2006-01-16 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
The first order definability of graphs with separators via the Ehrenfeucht game
Theoretical Computer Science | 2005-10-26 | Paper |
| scientific article; zbMATH DE number 2169359 (Why is no real title available?) | 2005-05-20 | Paper |
How complex are random graphs in first order logic?
Random Structures & Algorithms | 2005-04-21 | Paper |
On the lengths of symmetry breaking-preserving games on graphs
Theoretical Computer Science | 2004-10-27 | Paper |
| scientific article; zbMATH DE number 2059223 (Why is no real title available?) | 2004-03-16 | Paper |
Error reduction by parallel repetition - a negative result
Combinatorica | 2003-08-06 | Paper |
| scientific article; zbMATH DE number 1944410 (Why is no real title available?) | 2002-01-01 | Paper |
Arthur-Merlin games in Boolean decision trees
Journal of Computer and System Sciences | 2000-11-22 | Paper |
| scientific article; zbMATH DE number 1335880 (Why is no real title available?) | 2000-10-17 | Paper |
| scientific article; zbMATH DE number 1498640 (Why is no real title available?) | 2000-09-25 | Paper |
| scientific article; zbMATH DE number 1392301 (Why is no real title available?) | 2000-01-25 | Paper |
Towards the parallel repetition conjecture
Theoretical Computer Science | 1997-02-27 | Paper |
On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
Combinatorics, Probability and Computing | 1995-11-29 | Paper |
On a Hierarchy of Spectral Invariants for Graphs
(available as arXiv preprint) | N/A | Paper |
