10 citations · 15 across the 6 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.LO2024
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…
cs.CC2024
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…
cs.CC2024
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…