1 citations · 2 across the 3 of their papers we have counts for
Showing cs.LOShow all
2 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.LO2023★ 1 cited
From Quantifier Depth to Quantifier Number: Separating Structures with k Variables
Harry Vinall-Smeeth
Given two -element structures, and , which can be distinguished by a sentence of -variable first-order logic (), what is the minimum…