# One-way randomized complexity of (variants of) Gap-Hamming-Distance?

The $\textsf{GapHammingDistance}$ problem over $\{0,1\}^n$ is defined as follows: Alice (resp. Bob) is given an input $x\in\{0,1\}^n$ (resp, $y\in\{0,1\}^n$), under the promise that their Hamming distance satisfies $$\operatorname{d}_H(x,y) \in \left\{0,\dots,\frac{n}{2}-\sqrt{n}\right\}\cup\left\{\frac{n}{2}+\sqrt{n},\dots,n\right\}.$$ Their goal is to decide, wth probability at least $2/3$, whether $\operatorname{d}_H(x,y) \leq \frac{n}{2}-\sqrt{n}$; or $\operatorname{d}_H(x,y) \geq \frac{n}{2}+\sqrt{n}$.

A lower bound of $\Omega(n)$ is know for the one-way communication (randomized) version of this problem, as well as for the unbounded two-way communication.

Now, I am interested in the following two variants: is a linear lower bound (or a lower bound) known for the one-way randomized communication complexity of this problem, under the additional constraints:

1. (dominated version) $y \preceq x$, i.e. $y_i \leq x_i$ for all $i\in[n]$; or
2. (one-sided version) $\operatorname{d}_H(x,y) = \frac{n}{2}$; or $\operatorname{d}_H(x,y) \geq \frac{n}{2}+\sqrt{n}$

(I am mostly interested in the first)

I apologize if this is obvious, or follows easily from the proofs of the lower bounds for Gap-Hamming of Woodruff or Jayram-Kumar-Sivakumar; or the more recent ones for two-way communication. As far as I could tell, these proofs move the problem to the continuous, Gaussian setting, and it was unclear to me how to get the continuous version of the variants above.

Edit: As pointed out in the comments by Denis Pankratov, the first variant admits a trivial $O(\log n)$ upper bound (sending $\lvert x\rvert$ to Bob is enough).

• For your first question, hamming distance between $y$ and $x$ when $y \le x$ is just $|x| - |y|$, so it has a one-way protocol of communication cost $\le \log n$. – Denis Pankratov Oct 16 '15 at 23:41
• Oh, yes. I feel rather stupid. – Clement C. Oct 17 '15 at 3:05
• Should 2.3 be replaced with 2/3? $\;$ – user6973 Oct 17 '15 at 3:13
• @RickyDemer Yes, that was a typo -- fixed. – Clement C. Oct 17 '15 at 3:27