We show that for a relation and a function (with $m= O(\log n)${1/3}(f\circ g^n) = \Omega\left({1/3}(f) \cdot \left(\log\frac{1}{(M_g)} - O(\log n)\right)\right),where $f\circ g^n$ represents the composition of $f$ and $g^n$, $M_g$ is the sign matrix for $g$, $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ($\mathrm{R}_{1/3}(f\circ g^n)$) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$) with worst case error $\frac{1}{3}$. In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$,_{1/3}(f\circ m^n) = \Omega\left({1/3}(f) \cdot m\right),$_m:{0,1}^m\times {0,1}^m\rightarrow {0,1}$ is the Inner Product (modulo ) function and .

生成讲解博客的中文版本

生成AI智能校验的中文版本