research
∙
08/23/2023
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinat...
share
research
∙
08/13/2023
Exploration of graphs with excluded minors
We study the online graph exploration problem proposed by Kalyanasundara...
research
∙
06/01/2023
Algorithms Transcending the SAT-Symmetry Interface
Dedicated treatment of symmetries in satisfiability problems (SAT) is in...
research
∙
02/13/2023
Engineering a Preprocessor for Symmetry Detection
State-of-the-art solvers for symmetry detection in combinatorial objects...
research
∙
05/27/2022
Choiceless Polynomial Time with Witnessed Symmetric Choice
We extend Choiceless Polynomial Time (CPT), the currently only remaining...
research
∙
12/08/2021
Trainability for Universal GNNs Through Surgical Randomness
Message passing neural networks (MPNN) have provable limitations, which ...
research
∙
11/23/2021
A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension
We investigate the relationship between various isomorphism invariants f...
research
∙
09/15/2021
A Characterization of Individualization-Refinement Trees
Individualization-Refinement (IR) algorithms form the standard method an...
research
∙
08/10/2021
Parallel Computation of Combinatorial Symmetries
In practice symmetries of combinatorial structures are computed by trans...
research
∙
03/18/2021
Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case
Color refinement is a crucial subroutine in symmetry detection in theory...
research
∙
01/13/2021
Resolution with Symmetry Rule applied to Linear Equations
This paper considers the length of resolution proofs when using Krishnam...
research
∙
12/28/2020
Automorphism groups of graphs of bounded Hadwiger number
We determine the structure of automorphism groups of finite graphs of bo...
research
∙
11/18/2020
Engineering a Fast Probabilistic Isomorphism Test
We engineer a new probabilistic Monte-Carlo algorithm for isomorphism te...
research
∙
11/03/2020
Search Problems in Trees with Symmetries: near optimal traversal strategies for individualization-refinement algorithms
We define a search problem on trees that closely captures the backtracki...
research
∙
10/23/2020
Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time
In the quest for a logic capturing PTime the next natural classes of str...
research
∙
03/30/2020
On the Weisfeiler-Leman Dimension of Finite Groups
In comparison to graphs, combinatorial methods for the isomorphism probl...
research
∙
03/24/2020
Deep Weisfeiler Leman
We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL),...
research
∙
05/08/2019
Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm
We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-v...
research
∙
06/19/2018
A unifying method for the design of algorithms canonizing combinatorial objects
We devise a unified framework for the design of canonization algorithms....
research
∙
03/19/2018
An improved isomorphism test for bounded-tree-width graphs
We give a new fpt algorithm testing isomorphism of n-vertex graphs of tr...
research
∙
02/13/2018
A Faster Isomorphism Test for Graphs of Small Degree
Luks's algorithm (JCSS 1982) to test isomorphism of bounded degree graph...
research
∙
02/13/2018
Towards faster isomorphism tests for bounded-degree graphs
Luks' algorithm (JCSS 1982) to test isomorphism of bounded degree graphs...
research
∙
12/26/2017
Space-Efficient Algorithms for Longest Increasing Subsequence
Given a sequence of integers, we want to find a longest increasing subse...
research
∙
08/24/2017