Showing cs.LOShow all
2 papers · 1 filter
cs.LO2026
Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting
Moritz Lichter
At the core of the quest for a logic for PTime is a mismatch between algorithms making arbitrary choices and isomorphism-invariant logics. One approach to overcome this problem is…
cs.LO2025
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 wi…