2 papers
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…
cs.DB2025
A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
Stefan Mengel, Harry Vinall-Smeeth
Motivated by recent connections to factorised databases, we analyse the efficiency of representations by context free grammars (CFGs). Concretely, we prove a recent conjecture by K…