论文标题
局部功能的随机查询复杂性的紧密组成定理
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
论文作者
论文摘要
我们证明了有关组成函数的随机查询复杂性的两个新结果。首先，我们表明随机构图的猜想是错误的：有部分布尔函数$ f $和$ g $的家庭，使得$ r（f \ circ g）\ ll r（f）r（g）$。实际上，我们表明左侧的左侧可能比右侧小（尽管在我们的构造中，两侧的输入尺寸为$ f $）。 其次，我们证明，对于所有$ f $和$ g $，$ r（f \ circ g）=ω（\ m athop {noisyr}（f）\ cdot r（g））$，其中$ \ mathop {noisyr}（f）$是描述计算NoiSy Oracle ocy oracle ostuts的成本的措施。我们表明，此组合定理是其类型中最强的：对于所有$ r（f \ circ g）=ω$ m（\ cdot）$，对于所有$ f $ and $ g $，它都必须持有$ f $和$ g $的$ f $和$ g $，它必须持有$ \ mathop {noisyr}（noisyr}（f）（f）（f）=ω（m（m（m（m m，f））$ f $ for All $ f $。我们还给出了该度量的清晰表征$ \ MATHOP {NOISYR}（f）$：它满足$ \ Mathop {noisyr}（f）（f）=θ（r（f \ Circ gapmaj_n）/r（gapmaj_n））在$ n $ bit上。
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(f\circ g)\ll R(f) R(g)$. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$). Second, we show that for all $f$ and $g$, $R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))$, where $\mathop{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(\cdot)$ satisfying $R(f\circ g)=Ω(M(f)R(g))$ for all $f$ and $g$, it must hold that $\mathop{noisyR}(f)=Ω(M(f))$ for all $f$. We also give a clean characterization of the measure $\mathop{noisyR}(f)$: it satisfies $\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))$, where $n$ is the input size of $f$ and $gapmaj_n$ is the $\sqrt{n}$-gap majority function on $n$ bits.
