Reminder: This post contains 1001 words
· 3 min read
· by Xianbin
In this post, the error of a randomized protocol is at most \(\epsilon\) where \(\epsilon\) is some constant.
One-way Set Disjointness
\(\textbf{Theorem 1}\). The randomized one-way DISJ has communication complexity \(\Omega(n)\).
Proof. We reduce the problem DISJ to the problem INDEX. Let \((X, i)\) be the input instance of INDEX. For DISJ, Alice has \(X' = X\) and Bob has \(Y' = \mathbb{1}_i\) where \(\mathbb{1}_i = (0,0,\ldots,1, 0,\ldots)\) where only \(i\)-th coordinate of \(Y'\) has 1. It is easy to see that DISJ (\(X', Y') = 1\) if and only if \(X'_i = 0\). Then we reduce every protocol for INDEX to DISJ.
One-way Gap Hamming
The gap hamming \(\text{GH}_n\) is defined as follows. Alice has a string \(X = \{0,1\}^n\) and Bob has a string \(Y = \{0, 1\}^n\). The goal is to determine whether \(\lvert X- Y \vert \geq n/2 - c\sqrt{n}\) or \(\lvert X - Y \rvert \leq n/2 + c\sqrt{n}\) where \(c\) is a parameter that is independent of \(X, Y, n\).
\(\textbf{Theorem 2}\). The randomized one-way \(\text{GH}_n\) has communication complexity \(\Omega(n)\)
Reference
[1]. Woodruff, D.P., 2004, January. Optimal space lower bounds for all frequency moments. In SODA (Vol. 4, pp. 167-175).