6 citations · 16 across the 14 of their papers we have counts for
Showing 2016Show all
3 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 $…
cs.CC2016
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
Christoph Berkholz, Martin Grohe
In recent years, we have seen several approaches to the graph isomorphism problem based on "generic" mathematical programming or algebraic (Gröbner basis) techniques. For most of t…