9 citations · 15 across the 11 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.CC2016
Supercritical Space-Width Trade-offs for Resolution
Christoph Berkholz, Jakob Nordström
We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the…
cs.LO2016
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
Christoph Berkholz, Jakob Nordström
We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of -element structures that can be distinguished by a $…