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/10/2023
Limitations of Game Comonads via Homomorphism Indistinguishability
Abramsky, Dawar, and Wang (2017) introduced the pebbling comonad for k-v...
research
∙
01/30/2023
The Iteration Number of the Weisfeiler-Leman Algorithm
We prove new upper and lower bounds on the number of iterations the k-di...
research
∙
10/14/2022
Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting
At the core of the quest for a logic for PTime is a mismatch between alg...
research
∙
05/27/2022
Choiceless Polynomial Time with Witnessed Symmetric Choice
We extend Choiceless Polynomial Time (CPT), the currently only remaining...
research
∙
09/15/2021
Limitations of the Invertible-Map Equivalences
This note draws conclusions that arise by combining two recent papers, b...
research
∙
04/27/2021
Separating Rank Logic from Polynomial Time
In the search for a logic capturing polynomial time the most promising c...
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
∙
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
∙
04/13/2018