论文标题
通过窒息来提升平均决策树
Lifting to Parity Decision Trees Via Stifling
论文作者
论文摘要
我们表明，只要小巧的功能/关系/关系$ f \ circ g $，只要小巧的$ g $满足我们称之为固化的属性，则（部分）功能或关系$ f $ lifts的确定性决策树的复杂性$ f $ lifts tos nake chartial决策树（PDT）尺寸的复杂性。我们观察到，几个恒定大小的简单小工具，例如在3个输入位上索引，4个输入位上的内部产品，大多数在3个输入位和随机功能上，可以满足此属性。可以表明，现有的随机通信提升了定理（[[Göös，Pitassi，Watson。Sicomp'20]，[Chattopadhyay等人Sicomp'21]）意味着PDT-Size提升。但是，这种方法有两个缺点：首先，它们提起$ f $的随机决策树复杂性，当$ f $是部分功能甚至总搜索问题时，它们的确定性对应物的成倍小。其次，在这种提升定理中，小工具的大小与输入大小的对数大于$ f $。在当前研究的边界，将小工具尺寸降低到常数是一个重要的开放问题。 我们的结果表明，即使是随机的恒定小工具，也可以提升到PDT尺寸。 Further, 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., $\textit{Res}$($\oplus$), of the unsatisfiability of closely related constant-width CNF formulas.
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 \circ 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. It can be shown that existing randomized communication lifting theorems ([Göös, Pitassi, Watson. SICOMP'20], [Chattopadhyay et al. SICOMP'21]) imply PDT-size lifting. However there are two shortcomings of this approach: first they lift randomized decision tree complexity of $f$, which could be exponentially smaller than its deterministic counterpart when either $f$ is a partial function or even a total search problem. Second, the size of the gadgets in such lifting theorems are as large as logarithmic in the size of the input to $f$. Reducing the gadget size to a constant is an important open problem at the frontier of current research. Our result shows that even a random constant-size gadget does enable lifting to PDT size. Further, 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., $\textit{Res}$($\oplus$), of the unsatisfiability of closely related constant-width CNF formulas.
