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