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 &amp; \text{ if }\operatorname{d}_H(x,y) \leq \frac{n}{2}-\sqrt{n}\\
1 &amp; \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 &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 [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$.)
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.