C1: One-Way Communication Complexity

December 25, 2024

• One-way Set Disjointness
• One-way Gap Hamming
• Reference

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).