# Gap-Hamming with different “threshold” (i.e., not $n/2$)

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$.)

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