<p><em>After the OP's edit (see comments below), this answer is outdated and does not address the question. Leaving it for the said comments.</em></p>

<hr>

<p>This seems to be asking the same as in <a href="https://cstheory.stackexchange.com/questions/33072/gap-hamming-with-different-threshold-i-e-not-n-2">this question of mine</a> <em>(which only has a partial answer, fitting for a partial function)</em>. Quoting from the question:</p>

<blockquote>
  <p>[Consider, for $x,y\in\{0,1\}^n$] the partial function
  $$
\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$. </p>
</blockquote>

<p>As answered there, the general <em>one-sided</em> version is solved in the following paper of Egor Klenin and Alexander Kozachinsky [1], who show that (with your notations) $\tilde{\Theta}\!\left(\frac{t}{(1-\alpha)^2}\right)$ bits are necessary and sufficient.</p>

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

CC BY-SA 3.0
2017-11-15T16:44:16.330Z
I think I ask slightly different.  $1$ if $lower<d<upper$ and $0$ elsewhere.  Your function is more like $0$ if $d<lower$ and $1$ if $upper<d$. Right?
Turbo
CC BY-SA 3.0
2017-11-15T16:47:05.410Z
Mmh. Then you might want to check the inequalities in your question (at least one appears to be a typo), and further I don't see the direct relation with Gap-Hamming. Your question is no longer a promise problem, there is no gap? (In that case, it seems unlikely you won't have a trivial linear lower bound, for inputs "just at the limit" between 1- and 0-inputs)
Clement C.
CC BY-SA 3.0
2017-11-15T16:48:29.237Z
I think you are right. It is more like a modified equality problem. I expect the randomized communication complexity to be small if $t$ is small. At $t=0$ it is equality function. So I have modified my problem. Is this studied anywhere? Is there a good reference?
Turbo
CC BY-SA 3.0
2017-11-15T16:59:16.433Z
@Turbo I'd say some variant of $\textsf{Disjointness}$, as you want to check whether the intersection is within a certain range.(in particular, for $t=n$ and $\alpha\approx 1-1/n$ you get back $\textsf{Disjointness}$.
Clement C.
CC BY-SA 3.0
2017-11-15T17:09:38.790Z
That is valid point. I will check with Disjointness problem.
Turbo
CC BY-SA 3.0
2017-11-15T16:03:11.747Z
2017-11-15T17:01:24.883Z
2017-11-15T17:01:24.883Z
Clement C.
<p>Consider $(\alpha,t)$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $(1-\alpha)t\leq|x\oplus y|\leq (1+\alpha)t$ or not when $\alpha\in[0,1)$ and $0\leq t\leq n$ holds. The problem interpolates somewhere between an equality function and set disjointness problem.</p>

<ol>
<li>What is the deterministic and randomized communication complexity for $(\alpha,t)$-String distance?</li>
</ol>

<p>Consider $t$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $t\leq|x\oplus y|$ or not. </p>

<ol start="2">
<li>What is the deterministic and randomized communication complexity for $t$-String distance?</li>
</ol>

<communication-complexity>
String distance communication complexity
Turbo
# String distance communication complexity

(Asked by: username_0 on 2017-11-15)

Consider $(\alpha,t)$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $(1-\alpha)t\leq|x\oplus y|\leq (1+\alpha)t$ or not when $\alpha\in[0,1)$ and $0\leq t\leq n$ holds. The problem interpolates somewhere between an equality function and set disjointness problem.

1. What is the deterministic and randomized communication complexity for $(\alpha,t)$-String distance?

Consider $t$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $t\leq|x\oplus y|$ or not.

2. What is the deterministic and randomized communication complexity for $t$-String distance?

**Tags:** communication-complexity

---

## 1 answers

### Answer by username_1 on 2017-11-15. Score: 1

*After the OP's edit (see comments below), this answer is outdated and does not address the question. Leaving it for the said comments.*

---

This seems to be asking the same as in [this question of mine](https://cstheory.stackexchange.com/questions/33072/gap-hamming-with-different-threshold-i-e-not-n-2) *(which only has a partial answer, fitting for a partial function)*. Quoting from the question:

> [Consider, for $x,y\in\{0,1\}^n$] the partial function
> $$
> \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$.

As answered there, the general *one-sided* version is solved in the following paper of Egor Klenin and Alexander Kozachinsky [1], who show that (with your notations) $\tilde{\Theta}\!\left(\frac{t}{(1-\alpha)^2}\right)$ bits are necessary and sufficient.

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

> **Comments:**
> **username_0**: I think I ask slightly different.  $1$ if $lower<d<upper$ and $0$ elsewhere.  Your function is more like $0$ if $d<lower$ and $1$ if $upper<d$. Right?  
> **username_1**: Mmh. Then you might want to check the inequalities in your question (at least one appears to be a typo), and further I don't see the direct relation with Gap-Hamming. Your question is no longer a promise problem, there is no gap? (In that case, it seems unlikely you won't have a trivial linear lower bound, for inputs "just at the limit" between 1- and 0-inputs)  
> **username_0**: I think you are right. It is more like a modified equality problem. I expect the randomized communication complexity to be small if $t$ is small. At $t=0$ it is equality function. So I have modified my problem. Is this studied anywhere? Is there a good reference?  
> **username_1**: @Turbo I'd say some variant of $\textsf{Disjointness}$, as you want to check whether the intersection is within a certain range.(in particular, for $t=n$ and $\alpha\approx 1-1/n$ you get back $\textsf{Disjointness}$.  
> **username_0**: That is valid point. I will check with Disjointness problem.  

---

