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?