6 citations · 16 across the 14 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…
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…