0
$\begingroup$

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.

  1. What is the deterministic and randomized communication complexity for $t$-String distance?
$\endgroup$
1
$\begingroup$

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 (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] 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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – T.... Nov 15 '17 at 16:44
  • $\begingroup$ 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) $\endgroup$ – Clement C. Nov 15 '17 at 16:47
  • $\begingroup$ 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? $\endgroup$ – T.... Nov 15 '17 at 16:48
  • $\begingroup$ @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}$. $\endgroup$ – Clement C. Nov 15 '17 at 16:59
  • $\begingroup$ That is valid point. I will check with Disjointness problem. $\endgroup$ – T.... Nov 15 '17 at 17:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.