A Composition Theorem for Randomized Query Complexity
A Composition Theorem for Randomized Query Complexity
复制标题
随机查询复杂性的组合定理
DOI：
10.4230/lipics.fsttcs.2017.10
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Swagato Sanyal
中科院分区：
文献类型：
--
作者：
Anurag Anshu;Dmitry Gavinsky;Rahul Jain;Srijita Kundu;Troy Lee;Priyanka Mukhopadhyay;M. Santha;Swagato Sanyal
设错误概率$\epsilon$关系的随机查询复杂度表示为$R_\epsilon(\cdot)$。我们证明了对于任意关系$f \subseteq \{0,1\}^n \times \mathcal{R}$和布尔函数$g:\{0,1\}^m \rightarrow \{0,1\}$, $R_{1/3}(f\circ g^n) = \Omega(R_{4/9}(f)\cdot R_{1/2-1/n^4}(g))$，其中$f \circ g^n$是由$f$和$g$组合得到的关系。我们还展示了$R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=\Omega(\log n \cdot R_{4/9}(f) \cdot R_{1/3}(g))$，其中$g^\oplus_{O(\log n)}$是通过在$O(\log n)$位和$g^t$上组合xor函数得到的函数。
Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $R_{1/3}(f\circ g^n) = \Omega(R_{4/9}(f)\cdot R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. We also show that $R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=\Omega(\log n \cdot R_{4/9}(f) \cdot R_{1/3}(g))$, where $g^\oplus_{O(\log n)}$ is the function obtained by composing the xor function on $O(\log n)$ bits and $g^t$.
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
BPP 的查询到通信提升
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas