203 citations · 322 across the 18 of their papers we have counts for
4 papers · 1 filter
Trading inference effort versus size in CNF Knowledge Compilation
Matthew Gwynne, Oliver Kullmann
Knowledge Compilation (KC) studies compilation of boolean functions f into some formalism F, which allows to answer all queries of a certain kind in polynomial time. Due to its rel…
Hardness measures and resolution lower bounds
Olaf Beyersdorff, Oliver Kullmann
Various "hardness" measures have been studied for resolution, providing theoretical insight into the proof complexity of resolution and its fragments, as well as explanations for t…
On SAT representations of XOR constraints
Matthew Gwynne, Oliver Kullmann
We study the representation of systems S of linear equations over the two-element field (aka xor- or parity-constraints) via conjunctive normal forms F (boolean clause-sets). First…
Towards a theory of good SAT representations
Matthew Gwynne, Oliver Kullmann
We aim at providing a foundation of a theory of "good" SAT representations F of boolean functions f. We argue that the hierarchy UC_k of unit-refutation complete clause-sets of lev…