Following a previous question, 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] 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] (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$.)

  • $\begingroup$ There are additional results on Gap Hamming distance in arxiv.org/abs/1506.00273. But perhaps you're already aware of that work. $\endgroup$ – Robin Kothari Nov 13 '15 at 14:30
  • $\begingroup$ @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$. $\endgroup$ – Clement C. Nov 13 '15 at 15:10
  • $\begingroup$ 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}$) $\endgroup$ – Clement C. Nov 13 '15 at 15:13

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, 2016.

  • $\begingroup$ I think that will put you over the 1k threshold so you can see who voted in which way... $\endgroup$ – Tayfun Pay Aug 15 '17 at 23:08
  • $\begingroup$ @TayfunPay Err... thanks. Is that OK with the site policy to upvote for such a purpose, though? $\endgroup$ – Clement C. Aug 15 '17 at 23:42
  • $\begingroup$ 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. $\endgroup$ – Tayfun Pay Aug 17 '17 at 0:43

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.