<p>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}$.</p>

<p>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.</p>

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

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

<p>(I am mostly interested in the first)</p>

<p>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. </p>

<ul>
<li><a href="http://www.theoryofcomputing.org/articles/v004a006/" rel="nofollow">The One-Way Communication Complexity of Hamming Distance</a>, by T. S. Jayram, Ravi Kumar, and D. Sivakumar (2008)</li>
<li><a href="http://theoryofcomputing.org/articles/v008a008/" rel="nofollow">The Communication Complexity of Gap Hamming Distance</a>, by Alexander A. Sherstov (2012)</li>
</ul>

<p><strong>Edit:</strong> 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).</p>

CC BY-SA 3.0
2015-10-16T23:41:50.563Z
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
CC BY-SA 3.0
2015-10-17T03:05:19.633Z
Oh, yes. I feel rather stupid.
Clement C.
CC BY-SA 3.0
2015-10-17T03:27:37.797Z
@RickyDemer Yes, that was a typo -- fixed.
Clement C.
<lower-bounds><communication-complexity>
One-way randomized complexity of (variants of) Gap-Hamming-Distance?
Clement C.
# One-way randomized complexity of (variants of) Gap-Hamming-Distance?

(Asked by: username_0 on 2015-10-16)

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.

* [The One-Way Communication Complexity of Hamming Distance](http://www.theoryofcomputing.org/articles/v004a006/), by T. S. Jayram, Ravi Kumar, and D. Sivakumar (2008)
* [The Communication Complexity of Gap Hamming Distance](http://theoryofcomputing.org/articles/v008a008/), by Alexander A. Sherstov (2012)

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

**Tags:** lower-bounds, communication-complexity

> **Comments:**
> **username_1**: 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$.  
> **username_0**: Oh, yes. I feel rather stupid.  
> **username_0**: @RickyDemer Yes, that was a typo -- fixed.  

---

## 0 answers

