<p>As it turns out, the <em>one-sided</em> error case (public coin) was addressed in [KK16], which shows the communication complexity is then $\tilde{\Theta}\!\left(\frac{(t-g)^2}{t+g}\right)$ (the upper and lower bound are off only by a $\log(t-g)$ factor).</p>

<p>(so, for $\mathsf{GHD}_{n,2\sqrt{n},\sqrt{n}}$, the one-sided public-coin communication complexity is $\tilde{\Theta}\!\left(\sqrt{n}\right)$.)</p>

<p>[KK16] <em>One-sided error communication complexity of Gap Hamming Distance,</em> Egor Klenin and Alexander Kozachinsky. <a href="https://eccc.weizmann.ac.il/report/2016/173/" rel="noreferrer">ECCC TR16-173</a>, 2016.</p>

CC BY-SA 3.0
2017-08-15T23:08:59.037Z
I think that will put you over the 1k threshold so you can see who voted in which way...
Tayfun Pay
CC BY-SA 3.0
2017-08-15T23:42:16.243Z
@TayfunPay Err... thanks. Is that OK with the site policy to upvote for such a purpose, though?
Clement C.
CC BY-SA 3.0
2017-08-17T00:43:04.183Z
Well the site policy has been already broken thanks to the P!=NP discussion.. lol... It is like someone robs a bank but then he wonders whether or not it is ethical to take the few extra quarters that some vending machine spits out... In any case, it is all good.
Tayfun Pay
CC BY-SA 3.0
2017-06-03T17:36:54.623Z
2017-06-03T17:36:54.623Z
Clement C.
<p>Following a <a href="https://cstheory.stackexchange.com/questions/32836/one-way-randomized-complexity-of-variants-of-gap-hamming-distance">previous question</a>, I'm trying to get a better understanding of the parameters at play in $\textsf{Gap-Hamming}$. In the "standard" setting, we have
$x,y\in\{0,1\}^n$ and the partial function
$$
\textsf{GHD}_{n,n/2,\sqrt{n}} = \begin{cases}
0 &amp; \text{ if }\operatorname{d}_H(x,y) \leq \frac{n}{2}-\sqrt{n}\\
1 &amp; \text{ if }\operatorname{d}_H(x,y) \geq \frac{n}{2}+\sqrt{n}.
\end{cases}$$
This can be generalized to 
$$
\textsf{GHD}_{n,t,g} = \begin{cases}
0 &amp; \text{ if }\operatorname{d}_H(x,y) \leq t-g\\
1 &amp; \text{ if }\operatorname{d}_H(x,y) \geq t+g.
\end{cases}$$
Lemma 4.1 to Proposition 4.4 of <a href="http://arxiv.org/abs/1009.3460v3" rel="nofollow noreferrer">[CR10]</a> allow to get a lower bound on the communication complexity of $\textsf{GHD}_{n,t,g}$ for (most) of the settings of $t,g$. Another generalization is introduced and studied in <a href="http://eccc.hpi-web.de/report/2011/045/" rel="nofollow noreferrer">[BBM13]</a> (Lemma 2.5), $\textsf{EGHD}_{n,k,t}$, which corresponds to $\textsf{GHD}_{n,k/2,g}$ with the additional promise that that $\lvert x\rvert = \lvert y\rvert = k/2$.</p>

<p>However, as far as I could see none of the above covers the "corner cases" where $t$ is itself sublinear (and say, comparable to $g$), but $\lvert x\rvert, \lvert y\rvert$ are still arbitrary. Is the behaviour of the randomized communication complexity for e.g. $\textsf{GHD}_{n,2\sqrt{n},\sqrt{n}}$ obvious? </p>

<p>(I suppose two reasonable conjectures would be that the CC be either $\Omega(\sqrt{n})$ or $O(1)$ in this case, the first inspired by the difficulty of distinguish a coin with bias $\varepsilon$ from one with bias $2\varepsilon$ with less than $1/\varepsilon$ samples; the second because it "looks" easy, and a completely hazy feeling.However, and most likely because I'm missing something obvious, I don't really see which holds, nor how to get a general tradeoff that would cover the whole spectrum of $t,g$.)</p>

CC BY-SA 3.0
2015-11-13T14:30:04.130Z
There are additional results on Gap Hamming distance in http://arxiv.org/abs/1506.00273. But perhaps you're already aware of that work.
Robin Kothari
CC BY-SA 3.0
2015-11-13T15:10:57.997Z
@RobinKothari Thanks! I had somehow forgotten about their general GHD results (from Definition 2.8, and Lemmata 3.3). I need to look at it more carefully to see if that answers my question -- at first glance, I'm not sure, since their parameterization does impose a condition on the Hamming weights of $x,y$.
Clement C.
CC BY-SA 3.0
2015-11-13T15:13:48.840Z
Also, I think I have a rough sketch showing that the case $t=2\sqrt{n}$, $g=\sqrt{n}$ should have randomized communication complexity (or even public-coin SMP) $O(\log n)$. I need to doublecheck it carefully, though; and if it goes through I'd be biased towards thinking an $O(1)$ bound is more likely. (also, even if it holds, this approach probably won't give any "good" results for, say, $t= n^{1/4}$ and $g=n^{1/5}$)
Clement C.
<communication-complexity>
Gap-Hamming with different "threshold" (i.e., not $n/2$)
Clement C.
# Gap-Hamming with different "threshold" (i.e., not $n/2$)

(Asked by: username_0 on 2015-11-13)

Following a [previous question](https://cstheory.stackexchange.com/questions/32836/one-way-randomized-complexity-of-variants-of-gap-hamming-distance), I'm trying to get a better understanding of the parameters at play in $\textsf{Gap-Hamming}$. In the "standard" setting, we have
$x,y\in\{0,1\}^n$ and the partial function
$$
\textsf{GHD}\_{n,n/2,\sqrt{n}} = \begin{cases}
0 & \text{ if }\operatorname{d}\_H(x,y) \leq \frac{n}{2}-\sqrt{n}\\
1 & \text{ if }\operatorname{d}\_H(x,y) \geq \frac{n}{2}+\sqrt{n}.
\end{cases}$$
This can be generalized to
$$
\textsf{GHD}\_{n,t,g} = \begin{cases}
0 & \text{ if }\operatorname{d}\_H(x,y) \leq t-g\\
1 & \text{ if }\operatorname{d}\_H(x,y) \geq t+g.
\end{cases}$$
Lemma 4.1 to Proposition 4.4 of [[CR10]](http://arxiv.org/abs/1009.3460v3) allow to get a lower bound on the communication complexity of $\textsf{GHD}\_{n,t,g}$ for (most) of the settings of $t,g$. Another generalization is introduced and studied in [[BBM13]](http://eccc.hpi-web.de/report/2011/045/) (Lemma 2.5), $\textsf{EGHD}\_{n,k,t}$, which corresponds to $\textsf{GHD}\_{n,k/2,g}$ with the additional promise that that $\lvert x\rvert = \lvert y\rvert = k/2$.

However, as far as I could see none of the above covers the "corner cases" where $t$ is itself sublinear (and say, comparable to $g$), but $\lvert x\rvert, \lvert y\rvert$ are still arbitrary. Is the behaviour of the randomized communication complexity for e.g. $\textsf{GHD}\_{n,2\sqrt{n},\sqrt{n}}$ obvious?

(I suppose two reasonable conjectures would be that the CC be either $\Omega(\sqrt{n})$ or $O(1)$ in this case, the first inspired by the difficulty of distinguish a coin with bias $\varepsilon$ from one with bias $2\varepsilon$ with less than $1/\varepsilon$ samples; the second because it "looks" easy, and a completely hazy feeling.However, and most likely because I'm missing something obvious, I don't really see which holds, nor how to get a general tradeoff that would cover the whole spectrum of $t,g$.)

**Tags:** communication-complexity
> **Comments:**
> **username_1**: There are additional results on Gap Hamming distance in http://arxiv.org/abs/1506.00273. But perhaps you're already aware of that work.  
> **username_0**: @RobinKothari Thanks! I had somehow forgotten about their general GHD results (from Definition 2.8, and Lemmata 3.3). I need to look at it more carefully to see if that answers my question -- at first glance, I'm not sure, since their parameterization does impose a condition on the Hamming weights of $x,y$.  
> **username_0**: Also, I think I have a rough sketch showing that the case $t=2\sqrt{n}$, $g=\sqrt{n}$ should have randomized communication complexity (or even public-coin SMP) $O(\log n)$. I need to doublecheck it carefully, though; and if it goes through I'd be biased towards thinking an $O(1)$ bound is more likely. (also, even if it holds, this approach probably won't give any "good" results for, say, $t= n^{1/4}$ and $g=n^{1/5}$)  

---

## 1 answers

### Answer by username_0 on 2017-06-03. Score: 4 | Accepted answer

As it turns out, the *one-sided* error case (public coin) was addressed in [KK16], which shows the communication complexity is then $\tilde{\Theta}\!\left(\frac{(t-g)^2}{t+g}\right)$ (the upper and lower bound are off only by a $\log(t-g)$ factor).

(so, for $\mathsf{GHD}\_{n,2\sqrt{n},\sqrt{n}}$, the one-sided public-coin communication complexity is $\tilde{\Theta}\!\left(\sqrt{n}\right)$.)

[KK16] *One-sided error communication complexity of Gap Hamming Distance,* Egor Klenin and Alexander Kozachinsky. [ECCC TR16-173](https://eccc.weizmann.ac.il/report/2016/173/), 2016.

> **Comments:**
> **username_2**: I think that will put you over the 1k threshold so you can see who voted in which way...  
> **username_0**: @TayfunPay Err... thanks. Is that OK with the site policy to upvote for such a purpose, though?  
> **username_2**: Well the site policy has been already broken thanks to the P!=NP discussion.. lol... It is like someone robs a bank but then he wonders whether or not it is ethical to take the few extra quarters that some vending machine spits out... In any case, it is all good.  

---

