论文标题
强大的XOR引理，用于与有限的回合交流
Strong XOR Lemma for Communication with Bounded Rounds
论文作者
论文摘要
在本文中，我们证明了有界的两者随机通信的强大XOR引理。对于功能，$ f：\ nathcal {x} \ times \ mathcal {y} \ rightArrow \ {0,1 \} $，$ n $ -fold xor xor xor xor函数$ f^{\ oplus n}：\ natcal {x} $ n $输入对$（x_1，\ ldots，x_n，y_1，\ ldots，y_n）$ to $ n $ umpute bits $ f（x_1，y_1）\ oplus \ cdots \ cdots \ oplus f（x_n，y_n，y_n，y_n）$。我们证明，如果每个$ r $ round的通信协议都以$ 2/3 $计算$ f $的每个$ f $使用$ 2/3 $使用至少$ c $的通信，则使用$ f^{\ oplus n} $计算的任何$ r $ round协议，概率$ 1/2+\ exp（-o（n））$ c-1 \右）$位。当$ r $是常数而$ c $足够大时，这是$ω（n \ cdot c）$ bits。它与独立计算$ n $ bits $ f（x_i，y_i）$计算的琐碎协议的通信成本和成功概率相匹配，并独立输出其XOR，在$ n $中的恒定因素。 已经证明了类似的XOR引理的$ f $，可以通过界限[Shaltiel'03]来获得其通信下限。由于差异与与$ 2 $ - 数字通信协议的相关性[Viola-Wigderson'08]之间的相等性，我们的新XOR引理意味着先前的结果。
In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\{0,1\}$, the $n$-fold XOR function $f^{\oplus n}:\mathcal{X}^n\times \mathcal{Y}^n\rightarrow\{0,1\}$ maps $n$ input pairs $(X_1,\ldots,X_n,Y_1,\ldots,Y_n)$ to the XOR of the $n$ output bits $f(X_1,Y_1)\oplus \cdots \oplus f(X_n, Y_n)$. We prove that if every $r$-round communication protocols that computes $f$ with probability $2/3$ uses at least $C$ bits of communication, then any $r$-round protocol that computes $f^{\oplus n}$ with probability $1/2+\exp(-O(n))$ must use $n\cdot \left(r^{-O(r)}\cdot C-1\right)$ bits. When $r$ is a constant and $C$ is sufficiently large, this is $Ω(n\cdot C)$ bits. It matches the communication cost and the success probability of the trivial protocol that computes the $n$ bits $f(X_i,Y_i)$ independently and outputs their XOR, up to a constant factor in $n$. A similar XOR lemma has been proved for $f$ whose communication lower bound can be obtained via bounding the discrepancy [Shaltiel'03]. By the equivalence between the discrepancy and the correlation with $2$-bit communication protocols [Viola-Wigderson'08], our new XOR lemma implies the previous result.
