论文标题
许多样本在查询复杂性中的力量
The Power of Many Samples in Query Complexity
论文作者
论文摘要
布尔函数的随机查询复杂性$ r（f）$ $ f \ colon \ {0,1 \}^n \ to \ {0,1 \} $的著名表征（通过yao's minimax）（通过yao的minimax）表征（通过yao的minimax），以分配$ d_ $ $ d_ $ uptup $ -utput $ d_ uptut $ d_ uptup $ d_ uptup $ d_1的最小数量对$（D_0，D_1）$。我们问：如果我们允许从$ d_0 $或$ d_1 $中的许多样本进行查询访问，该任务会变得更容易吗？我们显示答案是否：存在一个硬对$（d_0，d_1）$，使得将$ d_0^\ infty $与$ d_1^\ infty $区分开来，需要$θ（r（f））$许多查询。作为一个应用程序，我们表明，对于任何包含的功能$ f \ circ g $，我们都有$ r（f \ circ g）\ geqω（\ mathrm {fbs}（fbs}（f）r（g））$，其中$ \ mathrm {fbs} $表示分数块灵敏度。
The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we allow query access to infinitely many samples from either $D_0$ or $D_1$? We show the answer is no: There exists a hard pair $(D_0,D_1)$ such that distinguishing $D_0^\infty$ from $D_1^\infty$ requires $Θ(R(f))$ many queries. As an application, we show that for any composed function $f\circ g$ we have $R(f\circ g) \geq Ω(\mathrm{fbs}(f)R(g))$ where $\mathrm{fbs}$ denotes fractional block sensitivity.
