Abstract
We show that the deterministic decision tree complexity of a (partial) function or relation f lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation f o g as long as the gadget g satisfies a property that we call stifling. We observe that several simple gadgets of constant size, like Indexing on 3 input bits, Inner Product on 4 input bits, Majority on 3 input bits and random functions, satisfy this property.
Further, via standard connections, it also yields the first systematic way of turning lower bounds on the width of tree-like resolution proofs of the unsatisfiability of constant-width CNF formulas to lower bounds on the size of tree-like proofs in the resolution with parity system, i.e., Res-Lin, of the unsatisfiability of closely related constant-width CNF formulas.