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

  • 2
    $\begingroup$ 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$. $\endgroup$ Oct 16 '15 at 23:41
  • $\begingroup$ Oh, yes. I feel rather stupid. $\endgroup$
    – Clement C.
    Oct 17 '15 at 3:05
  • $\begingroup$ Should 2.3 be replaced with 2/3? $\;$ $\endgroup$
    – user6973
    Oct 17 '15 at 3:13
  • $\begingroup$ @RickyDemer Yes, that was a typo -- fixed. $\endgroup$
    – Clement C.
    Oct 17 '15 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.