10 citations · 15 across the 6 of their papers we have counts for
14 papers
Weisfeiler-Leman on graphs of small twin-width
Irene Heinrich, Moritz Lichter, Klara Pakhomenko +1
Twin-width is a graph parameter introduced in the context of first-order model checking, and has since become a central parameter in algorithmic graph theory. While many algorithmi…
Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
Christoph Berkholz, Moritz Lichter, Harry Vinall-Smeeth
We study the refutation complexity of graph isomorphism in the tree-like resolution calculus. Torán and Wörz (TOCL 2023) showed that there is a resolution refutation of narrow widt…
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
Moritz Lichter, Benedikt Pago
We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tract…
Computational complexity of the Weisfeiler-Leman dimension
Moritz Lichter, Simon Raßmann, Pascal Schweitzer
The Weisfeiler-Leman dimension of a graph is the least number such that the -dimensional Weisfeiler-Leman algorithm distinguishes from every other non-isomorphic gra…
Limitations of Game Comonads via Homomorphism Indistinguishability
Moritz Lichter, Benedikt Pago, Tim Seppelt
Abramsky, Dawar, and Wang (2017) introduced the pebbling comonad for k-variable counting logic and thereby initiated a line of work that imports category theoretic machinery to fin…
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe, Moritz Lichter, Daniel Neuen +1
The -dimensional Weisfeiler-Leman (-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applic…