论文标题
决策树的复杂性与块灵敏度和程度
Decision Tree Complexity versus Block Sensitivity and Degree
论文作者
论文摘要
决策树的复杂性与布尔功能的各种其他复杂性度量之间的关系是计算复杂性研究的繁荣话题。众所周知，决策树的复杂性在上面是块灵敏度和多项式程度的立方体。但是，决策树的复杂性与已知布尔函数见证的每个块灵敏度和程度之间的最大分离是二次的。在这项工作中，我们研究了现有的立方上限的紧密度。 我们改善了许多有趣的布尔功能类别的立方上限。我们表明，对于图形属性和具有恒定数量交替数量的函数，可以将两个立方上限提高到二次。我们定义了一类布尔函数，称为斑马函数，该功能包括布尔函数，其中每个单调路径（从0^n到1^n）具有相等数量的交替数量。该类包含对称和单调作为其子类作用。我们表明，对于任何斑马函数，决策树的复杂性最多都是块灵敏度的平方，证书复杂性最多是程度的平方。 最后，我们使用g {Ö} {Ö}，Pitassi和Watson的沟通复杂性提升理论表明，证明对所有功能的决策树复杂性进行改进的上限的任务在于可能更容易的任务，即在所有输入函数上都可以证明，在每个功能上证明了相似的上限复杂性的相似的上限，以供所有功能进行交流。特别是，这意味着要限制决策树的复杂性，它足以限制较小的措施，例如奇偶校验树的复杂性，Sub -Cube决策树的复杂性和决策树等级，这些措施是根据可以通过通信协议有效模拟的模型来定义的。
Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. It is known that decision tree complexity is bounded above by the cube of block sensitivity, and the cube of polynomial degree. However, the widest separation between decision tree complexity and each of block sensitivity and degree that is witnessed by known Boolean functions is quadratic. In this work, we investigate the tightness of the existing cubic upper bounds. We improve the cubic upper bounds for many interesting classes of Boolean functions. We show that for graph properties and for functions with a constant number of alternations, both of the cubic upper bounds can be improved to quadratic. We define a class of Boolean functions, which we call the zebra functions, that comprises Boolean functions where each monotone path from 0^n to 1^n has an equal number of alternations. This class contains the symmetric and monotone functions as its subclasses. We show that for any zebra function, decision tree complexity is at most the square of block sensitivity, and certificate complexity is at most the square of degree. Finally, we show using a lifting theorem of communication complexity by G{ö}{ö}s, Pitassi and Watson that the task of proving an improved upper bound on the decision tree complexity for all functions is in a sense equivalent to the potentially easier task of proving a similar upper bound on communication complexity for each bi-partition of the input variables, for all functions. In particular, this implies that to bound the decision tree complexity it suffices to bound smaller measures like parity decision tree complexity, subcube decision tree complexity and decision tree rank, that are defined in terms of models that can be efficiently simulated by communication protocols.
