Separating decision tree complexity from subcube partition complexity
Separating decision tree complexity from subcube partition complexity
复制标题
将决策树复杂性与子立方体划分复杂性分开
DOI：
10.4230/lipics.approx-random.2015.915
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Santha
中科院分区：
文献类型：
--
作者：
Robin Kothari;David Racicot;M. Santha
计算的子立方体分区模型至少与决策树一样强大，但是这些模型之间没有分离。我们表明，存在一个函数，其确定性的子立方体分区复杂性在渐近的决策树复杂性上渐近小，它解决了Friedgut，Kahn和Wigderson（2002）的开放问题。我们的下限是基于最初引入的信息理论技术，该技术是递归多数函数的随机决策树复杂性的下限。
我们还表明，公共胶木分区绑定了，最知名的下限方法是随机决策树复杂性包含的其他一般技术，例如块灵敏度，近似程度，随机证书复杂性和经典的对手界，也是下限的随机子立方体分区复杂。这表明所有这些下限技术无法证明随机决策树复杂性的最佳下限，这回答了Jain和Klauck（2010）和Jain，Lee和Vishnoi（2014）的一个开放问题。
The subcube partition model of computation is at least as powerful as decision trees but no separation between these models was known. We show that there exists a function whose deterministic subcube partition complexity is asymptotically smaller than its randomized decision tree complexity, resolving an open problem of Friedgut, Kahn, and Wigderson (2002). Our lower bound is based on the information-theoretic techniques first introduced to lower bound the randomized decision tree complexity of the recursive majority function.
We also show that the public-coin partition bound, the best known lower bound method for randomized decision tree complexity subsuming other general techniques such as block sensitivity, approximate degree, randomized certificate complexity, and the classical adversary bound, also lower bounds randomized subcube partition complexity. This shows that all these lower bound techniques cannot prove optimal lower bounds for randomized decision tree complexity, which answers an open question of Jain and Klauck (2010) and Jain, Lee, and Vishnoi (2014).
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas