1 citations · 1 across the 3 of their papers we have counts for
3 papers
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…
cs.AI2014★ 1 cited
The Propagation Depth of Local Consistency
Christoph Berkholz
We establish optimal bounds on the number of nested propagation steps in -consistency tests. It is known that local consistency algorithms such as arc-, path- and -consistenc…