6 citations · 16 across the 14 of their papers we have counts for
20 papers
Restructuring Tree Decision Diagrams
Christoph Berkholz, Matthäus Micun, Igor Razgon
Tree Decision Diagrams (TDDs) are a data structure recently introduced by Capelli et al. (SAT 2026). They are structured along a vtree and the size of their canonical form lies bet…
Proof Systems Based on Structured Circuits
Matthäus Micun, Christoph Berkholz
Since their introduction by Atserias, Kolaitis, and Vardi in 2004, proof systems where each line is represented by an ordered binary decision diagram (OBDD) have been intensively s…
Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy
Christoph Berkholz, Harry Vinall-Smeeth
A common theme in factorised databases and knowledge compilation is the representation of solution sets in a useful yet succinct data structure. In this paper, we study the represe…
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…
A dichotomy for succinct representations of homomorphisms
Christoph Berkholz, Harry Vinall-Smeeth
The task of computing homomorphisms between two finite relational structures and is a well-studied question with numerous applications. Since the set $\…
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
Christoph Berkholz, Nicole Schweikardt
Marx (STOC~2010, J.~ACM 2013) introduced the notion of submodular width of a conjunctive query (CQ) and showed that for any class of Boolean CQs of bounded submodular width, th…
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
Nofar Carmeli, Shai Zeevi, Christoph Berkholz +2
As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tr…
Answering UCQs under updates and in the presence of integrity constraints
Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
We investigate the query evaluation problem for fixed queries over fully dynamic databases where tuples can be inserted or deleted. The task is to design a dynamic data structure t…
Answering FO+MOD queries under updates on bounded degree databases
Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
We investigate the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that…
Answering Conjunctive Queries under Updates
Christoph Berkholz, Jens Keppeler, Nicole Schweikardt
We consider the task of enumerating and counting answers to -ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples. We exhibit…
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…
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 $…
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…
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Christoph Berkholz, Paul Bonsma, Martin Grohe
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to f…
Limitations of Algebraic Approaches to Graph Isomorphism Testing
Christoph Berkholz, Martin Grohe
We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Gröbner basis computation. The idea of these algorithms is to encode two graph…
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…
On the speed of constraint propagation and the time complexity of arc consistency testing
Christoph Berkholz, Oleg Verbitsky
Establishing arc consistency on two relational structures is one of the most popular heuristics for the constraint satisfaction problem. We aim at determining the time complexity o…
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy
Christoph Berkholz, Andreas Krebs, Oleg Verbitsky
Given two structures and distinguishable in $\fo k$ (first-order logic with variables), let denote the minimum alternation depth of a $\fo k$ formula disting…
Lower Bounds for Existential Pebble Games and k-Consistency Tests
Christoph Berkholz
The existential k-pebble game characterizes the expressive power of the existential-positive k-variable fragment of first-order logic on finite structures. The winner of the existe…
On the Complexity of Finding Narrow Proofs
Christoph Berkholz
We study the complexity of the following "resolution width problem": Does a given 3-CNF have a resolution refutation of width k? We prove that the problem cannot be decided in time…