# Nondeterministic communication complexity of Hamming distance

It is something that I think should be known: what is nondeterministic communication complexity of following task:

is $H(x,y) \geq k$?

There is an obvious upper bound $k \log(n)$. I would expect this to be tight up to a $o(\log(n))$ additive term (for small $k$). Is this known?

• A slightly better upper bound is $\log \binom{n}{k}$. – András Salamon Jun 8 '16 at 14:49