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?
Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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$
    – Turbo
    Nov 15, 2017 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, 2017 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$
    – Turbo
    Nov 15, 2017 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, 2017 at 16:59
  • $\begingroup$ That is valid point. I will check with Disjointness problem. $\endgroup$
    – Turbo
    Nov 15, 2017 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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