Towards Better Separation between Deterministic and Randomized Query Complexity
Towards Better Separation between Deterministic and Randomized Query Complexity
复制标题
更好地分离确定性和随机查询复杂性
DOI：
10.4230/lipics.fsttcs.2015.206
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Swagato Sanyal
中科院分区：
文献类型：
--
作者：
Sagnik Mukhopadhyay;Swagato Sanyal
我们表明存在一个布尔函数$ f $，该函数在确定性查询复杂性$（d（f））$，随机零错误查询复杂性$（r_0（f））$和随机的单侧错误查询复杂性中观察到以下分隔$（r_1（f））$：$ r_1（f）= \ widetilde {o}（\ sqrt {d（f）}）$和$ r_0（f）= \ widetilde {o}（d（f））^{3/4} $。这驳斥了Saks和Wigderson对任何布尔函数$ f $，$ r_0（f）= \ omega（{d（f）}）^{0.753 ..} $的猜想。对于任何布尔功能，这也显示出$ r_1（f）$和$ d（f）$之间的最大分离。函数$ f $由g {\“ {o}} {\” {o}} S，pitassi和沃森（Watson）定义，他们研究了它，以显示确定性决策树复杂性与明确的非确定性决策树的复杂性之间的分离。与我们独立于我们，Ambainis等人证明了$ f $ f $ certify最佳（二次）$ d（f）$和$ r_0（f）$以及$ r_0（f）$和$之间的多项式分隔之间的不同变体R_1（F）$。被视为分离结果，我们的结果被Ambainis等人的结果所归。但是，尽管Ambainis等人的工作中考虑的功能是$ f $的不同变体，但我们与原始函数$ f $本身一起工作。
We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$ and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by Saks and Wigderson that for any Boolean function $f$, $R_0(f)=\Omega({D(f)})^{0.753..}$. This also shows widest separation between $R_1(f)$ and $D(f)$ for any Boolean function. The function $F$ was defined by G{\"{o}}{\"{o}}s, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function $F$ certify optimal (quadratic) separation between $D(f)$ and $R_0(f)$, and polynomial separation between $R_0(f)$ and $R_1(f)$. Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considerd in the work of Ambainis et al are different variants of $F$, we work with the original function $F$ itself.
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas